1007. 素数对猜想 (20)

让我们定义 d_n 为：d_n = p_n+1 - p_n，其中 p_i 是第i个素数。显然有 d₁=1 且对于n>1有 d_n 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 10⁵)，请计算不超过N的满足猜想的素数对的个数。

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例： 20 输出样例： 4

#include <stdio.h>

int judge(int a){     if(a % 2 == 0 && a != 2)return 0;      for(int i = 3; i * i <= a; i++)if(a % i == 0)return 0;         return a != 1; } int main(void){   int num=0;   int a[50001]={0};   scanf("%d",&num);   int cnt=1;   a[0]=2;   for(int i=3;i<=num;i+=2)if(judge(i)==1)a[cnt++]=i;   int sum=0;   for(int j=0;j<=(cnt-2);j++){       if((a[j+1]-a[j])==2)sum++;   }   printf("%d",sum);   return 0;

}

#include <stdio.h> #include <stdlib.h> #include <malloc.h> int prime(int a[],int n)   {       int i,j,k,x,num,*b;       n++;       n/=2;       b=(int *)malloc(sizeof(int)*(n+1)*2);       a[0]=2;       a[1]=3;       num=2;       for (i=1;i<=2*n;i++)           b[i]=0;       for (i=3;i<=n;i+=3)           for (j=0;j<2;j++)           {               x=2*(i+j)-1;               while (b[x]==0)               {                   a[num++]=x;                   for (k=x;k<=2*n;k+=x)                       b[k]=1;               }           }       return num;   }   int main(void){   int num=0;   int a[50001]={0};   scanf("%d",&num);   a[0]=2;   int cnt=prime(a,num);   int sum=0;   for(int j=0;j<=(cnt-2);j++){       if((a[j+1]-a[j])==2)sum++;   }   printf("%d",sum);   return 0; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include <stdio.h> int isprime(int n) { for (int i=2;i<=sqrt(n);i++) { if (n%i==0) return 0; } return 1; } int main(void){ int num=0; int a[50001]={0}; scanf("%d",&num); int cnt=1; a[0]=2; for(int i=3;i<=num;i+=2)if(isprime(i)==1)a[cnt++]=i; int sum=0; for(int j=0;j<=(cnt-2);j++){ if((a[j+1]-a[j])==2)sum++; } printf("%d",sum); return 0; }