计数数字 <= N，在C ++中与素数计数的差为> = K
给定两个整数N和K，目标是找到数字的数量，使它们遵循以下条件：
数<=N
|数字计数|>=K其中count是小于或等于Number的质数个数。
例如
输入值
N = 5, K = 2输出结果
Count of numbers < = N whose difference with the count of primes upto them is > = K are: 2
说明
The numbers that follow the conditions are: 5 ( 5−2>=2 ) and 4 ( 4−2>=2 )
输入值
N = 10, K = 6输出结果
Count of numbers < = N whose difference with the count of primes upto them is > = K are: 1
说明
The numbers that follow the conditions are: 10 ( 10−4>=6 )
以下程序中使用的方法如下-
在这种方法中，我们将使用二进制搜索来减少计算量。如果最多num的素数计数为count1，而对于num+1的质数计数为count2。然后差异num+1-count2>=num-count1。因此，如果num有效，则num+1也将是valid.For使用符合条件的二进制搜索找到的第一个数字，例如“num”，然后“num”+1也将遵循相同的条件。这样，将计算从num到N之间的所有数字。
将变量N和K作为输入。
数组arr[]用于存储素数的计数，直到i将存储在索引i处。
功能set_prime()更新数组arr[]以存储素数计数。
数组check[i]如果i为质数则为true，否则为false。
将check[0]=check[1]=false设置为非素数。
从索引i=2遍历检查到i*i<size(1000001)。并且如果任何check[i]为1，则数字为素数，然后将所有check[j]的值从j=i*2设为0到j<size。
现在使用for循环遍历arr[]并对其进行更新。所有计数都达到arr[i]=arr[i-1]。如果arr[i]本身是素数，则该计数将增加1。设置arr[i]++。
功能total(intN,intK)取N和K并返回数字<=N的数量，其与素数的差值等于>=K。
呼叫set_prime()。
取temp_1=1和temp_2=N。将初始计数设为0。
现在使用二进制搜索，在while循环中使用set=（temp_1+temp_2）>>1（（first+last）/2）。
如果set-arr[set]>=K，则满足条件，用set和temp_2=set-1更新计数。
否则，请设置temp_1=temp_1+1。
最后设置为最小有效数字N-count+1或0。
在所有循环结束时，返回计数作为结果。
示例
#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;
}输出结果如果我们运行上面的代码，它将生成以下输出-
Count of numbers < = N whose difference with the count of primes upto them is > = K are: 4