题目描述
让我们定义d n 为
，其中p i p_{i}pi是第i ii个素数。显然有d 1 = 1，且对于n 有d n 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<
)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
思路解析
- c++
这道题目的关键就在于找素数，用for循环判断每个数是不是素数，如果是再与前一个素数对比，若差值为2则计数count加1。
素数的查找可以定义一个函数，对输入进来的数先开方得到k kk，然后做for循环到k kk，如果能被整除则不是素数。这里要注意任何数除1都能被整除，所以i要从2开始。
如果没有找到素数的话i ii就会大于k kk。如果输入的待验证数是1，则开方向下取整k = 1 k=1k=1，输入的待验证数是2、3同理。
- python
上述C++的思想python实现就炸了，超时了，因此想了好久，后来还是百度去看看找素数的时间复杂度能不能降到O ( n ) O(n)O(n)，没想到还真有，大概的意思就是先创建一个数组all_num(2-input_num)，对里面每个数只判断一遍是不是素数，判断的依据就是如果一个数是之前素数的倍数，那这个数就一定不是素数(由于2是素数，所以二的倍数全部设置为0，依此类推，如果循环到某个数大于0，就一定不是之前某个素数的倍数，就是一个素数啦)。
有点绕，具体可以看代码。
C++实现
#include<stdio.h> #include<math.h> int issushu(int num){ int i; int k = (int)sqrt(num); for(i=2; i<=k;i++){ if(num%i==0){ return 0; } } if(i>k){ return 1; } } int main(){ int input_num; int p_nn = 0; int p_n = 0; int count_num = 0; scanf("%d", &input_num); for(int i=0; i<=input_num; i++){ if(issushu(i)){ p_n = p_nn; p_nn = i; if(p_nn-p_n==2){ count_num++; } } } printf("%d", count_num); }
Python实现
input_num = int(input()) all_num = [i for i in range(0, input_num+1)] count = 0 p_n = 1 for i in all_num: if all_num[i] > 1: for j in range(2*i, input_num+1, i): all_num[j]=0 if (all_num[i]-p_n)==2: count += 1 p_n = all_num[i] print(count)
