Đếm số ≤ N mà hiệu với số lượng số nguyên tố đến nó ≥ K trong C++

Cho hai số nguyên N và K, mục tiêu là tìm số lượng các số sao cho chúng tuân theo các điều kiện sau:

Số ≤ N
| Số - count | ≥ K, trong đó count là số lượng số nguyên tố nhỏ hơn hoặc bằng Số.

Ví dụ

Đầu vào

N = 5, K = 2

Đầu ra

Số lượng số ≤ N mà hiệu với số nguyên tố đến nó ≥ K là: 2

Giải thích

Các số thỏa mãn điều kiện là: 5 (5-2≥2) và 4 (4-2≥2)

Đầu vào

N = 10, K = 6

Đầu ra

Số lượng số ≤ N mà hiệu với số nguyên tố đến nó ≥ K là: 1

Giải thích

Các số thỏa mãn điều kiện là: 10 (10-4≥6)

Phương pháp sử dụng

Trong phương pháp này, chúng ta sẽ sử dụng tìm kiếm nhị phân để giảm thiểu phép tính. Nếu số lượng số nguyên tố đến num là count1 và cho số num+1 số lượng này là count2. Khi đó hiệu num+1-count2 ≥ num-count1. Vì vậy nếu num hợp lệ, num+1 cũng sẽ hợp lệ. Đối với số đầu tiên tìm được, gọi là num bằng tìm kiếm nhị phân mà tuân theo điều kiện, thì num+1 cũng sẽ tuân theo cùng điều kiện. Theo cách này, tất cả các số từ num đến N sẽ được đếm.

Nhận biến N và K làm đầu vào.
Mảng arr[] dùng để lưu số lượng số nguyên tố đến i sẽ được lưu tại chỉ số i.
Hàm set_prime() cập nhật mảng arr[] để lưu số lượng số nguyên tố.
Mảng check[i] lưu true nếu i là số nguyên tố ngược lại lưu false.
Đặt check[0]=check[1] = false vì chúng không phải số nguyên tố.
Duyệt check từ chỉ số i=2 đến i*i<size(1000001). Và nếu bất kỳ check[i] là 1, số là nguyên tố thì đặt tất cả check[j] bằng 0 từ j=i*2 đến j<size.
Bây giờ duyệt arr[] bằng vòng lặp for và cập nhật nó. Tất cả số lượng đến arr[i]=arr[i-1]. Nếu arr[i] chính nó là số nguyên tố thì số lượng đó sẽ tăng 1. Đặt arr[i]++.
Hàm total(int N, int K) nhận N và K và trả về số lượng số ≤ N mà hiệu với số lượng số nguyên tố đến chúng ≥ K.
Gọi set_prime().
Lấy temp_1=1 và temp_2=N. Khởi tạo biến đếm ban đầu là 0.
Bây giờ sử dụng tìm kiếm nhị phân, trong vòng lặp while lấy set = (temp_1 + temp_2) >> 1 ((first+last)/2).
Nếu set - arr[set] ≥ K thì điều kiện được thỏa mãn, cập nhật biến đếm với set và temp_2 = set - 1.
Ngược lại đặt temp_1 = set + 1.
Cuối cùng đặt biến đếm là số hợp lệ nhỏ nhất N - count + 1 hoặc 0.
Cuối cùng của tất cả vòng lặp trả về biến đếm làm kết quả.

Ví dụ mã

#include <bits/stdc++.h> 
using namespace std; 
#define size 1000001 

int arr[size];

void set_prime() {
    bool check[size];
    memset(check, 1, sizeof(check));
    check[0] = 0;
    check[1] = 0;
    
    for (int i = 2; i * i < size; i++) {
        if (check[i] == 1) {
            for (int j = i * 2; j < size; j += i) {
                check[j] = 0;
            }
        }
    }
    
    for (int i = 1; i < size; i++) {
        arr[i] = arr[i - 1];
        if (check[i] == 1) {
            arr[i]++;
        }
    }
}

int total(int N, int K) {
    set_prime();
    int temp_1 = 1;
    int temp_2 = N;
    int count = 0;
    
    while (temp_1 <= temp_2) {
        int set = (temp_1 + temp_2) >> 1;
        if (set - arr[set] >= K) {
            count = set;
            temp_2 = set - 1;
        } else {
            temp_1 = set + 1;
        }
    }
    
    count = (count ? N - count + 1 : 0);
    return count;
}

int main() {
    int N = 12, K = 5;
    cout << "Số lượng số ≤ N mà hiệu với số nguyên tố đến nó ≥ K là: " << total(N, K);
    return 0;
}

Đầu ra

Nếu chạy mã trên, sẽ tạo ra đầu ra sau:

Số lượng số ≤ N mà hiệu với số nguyên tố đến nó ≥ K là: 4