让我们定义dn为:dn=p n+1−p n,其中p i是第i个素数。显然有d 1 =1,且对于n>1有d n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10 5),请计算不超过N的满足猜想的素数对的个数。
输入在一行给出正整数N。
输出格式:在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:20
输出样例:4
代码:思路:写一个素数判断函数,找出所用小于n的素数,统计有几对相邻的素数的差为2
#include#include #include #include #include using namespace std; int maxn = 100005; int judge(int k){//素数判断函数 for(int i = 2 ; i <= sqrt(k) ; i++) if(k % i == 0) return 0; return 1; } int main(){ int t[maxn]; int n , count1 = 0 , temp = 0; cin>>n; for(int i = 2 ; i <= n ; i++)//统计小于n的有多少素数 if(judge(i)) t[count1++] = i; for(int i = 0 ; i < count1 ; i++)//统计有几对相邻素数差为2 if(t[i+1] - t[i] == 2) temp++; cout< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)