Đếm số <=N có hiệu số với số nguyên tố tính đến chúng là> =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 dưới đây -

Số <=N
| Số-đếm |> =K Trong đó số đếm là số các số nguyên tố nhỏ hơn hoặc bằng Số.

Ví dụ

Đầu vào

N = 5, K = 2

Đầu ra

Count of numbers < = N whose difference with the count of primes upto them is > = K are: 2

Giải thích

The numbers that follow the conditions are:
5 ( 5−2>=2 ) and 4 ( 4−2>=2 )

Đầu vào

N = 10, K = 6

Đầu ra

Count of numbers < = N whose difference with the count of primes upto them
is > = K are: 1

Giải thích

The numbers that follow the conditions are:
10 ( 10−4>=6 )

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Trong cách tiếp cận này, chúng tôi sẽ sử dụng tìm kiếm nhị phân để giảm các phép tính của chúng tôi. Nếu số lượng các số nguyên tố lên đến num là count1 và đối với số num + 1 thì số đếm này là count2. Khi đó hiệu số 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 được tìm thấy, hãy nói "num" bằng cách sử dụng tìm kiếm nhị phân tuân theo điều kiện, sau đó ‘num’ + 1 cũng sẽ tuân theo điều kiện tương tự. Bằng cách này, tất cả các số từ num đến N sẽ được tính.

Lấy các biến N và K làm đầu vào.
Mảng arr [] được sử dụng để lưu trữ số lượng các số nguyên tố tối đa i sẽ được lưu trữ tại chỉ mục i.
Hàm set_prime () cập nhật mảng arr [] để lưu trữ số lượng các số nguyên tố.
Kiểm tra mảng [i] lưu trữ đúng nếu tôi là số nguyên tố còn lại lưu trữ sai.
Đặt check [0] =check [1] =false vì chúng không phải là số nguyên tố.
Kiểm tra ngược từ chỉ mục i =2 đến i * i
Bây giờ hãy duyệt arr [] bằng cách sử dụng vòng lặp for và cập nhật nó. Tất cả đều được tính đến arr [i] =arr [i − 1]. Nếu bản thân arr [i] là số nguyên tố thì số đó sẽ tăng lên 1. Đặt arr [i] ++.
Hàm tổng (int N, int K) nhận N và K và trả về Số lượng các số <=N có hiệu số với số lượng các số nguyên tố cho đến chúng là> =K.
Gọi set_prime ().
Lấy temp_1 =1 và temp_2 =N. Lấy số lượng ban đầu là 0.
Hiện đang 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] là> =K thì điều kiện được đáp ứng, cập nhật số lượng với set và temp_2 =set − 1.
Nếu không, hãy đặt temp_1 =temp_1 + 1.
Ở cuối tập hợp được tính là số hợp lệ tối thiểu N-count + 1 hoặc 0.
Kết quả là ở cuối tất cả các vòng lặp.

Ví dụ

#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<<"Count of numbers < = N whose difference with the count of primes upto them is > = K are: "<<total(N, K);
   return 0;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count of numbers < = N whose difference with the count of primes upto them is > = K are: 4