数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 统计小于等于 N 的数字，其与小于等于该数字的素数个数之差大于等于 K
给定两个整数 N 和 K，目标是找到满足以下条件的数字的个数：
数字 <= N
| 数字 - 计数 | >= K，其中计数是小于等于数字的素数的个数。
例如
输入
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 也有效。对于使用二分查找找到的第一个满足条件的数字，例如 '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
现在使用 for 循环遍历 arr[] 并更新它。所有计数都更新为 arr[i] = arr[i-1]。如果 arr[i] 本身是素数，则该计数将增加 1。设置 arr[i]++。
函数 total(int N, int K) 获取 N 和 K 并返回小于等于 N 的数字的个数，其与小于等于该数字的素数个数之差大于等于 K。
调用 set_prime()。
将 temp_1 = 1 和 temp_2 = N。将初始计数设置为 0。
现在使用二分查找，在 while 循环中设置 = (temp_1 + temp_2) >> 1 ((first+last) /2)。
如果 set - arr[set] >= K，则满足条件，将计数更新为 set 并将 temp_2 = set - 1。
否则，将 temp_1 = temp_1 + 1。
最后将计数设置为最小有效数字 N - 计数 + 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
111 次查看
