[TOC] ### 题目描述 1007 素数对猜想。 题目：让我们定义 dn 为：dn = pn+1 - pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N (< 105)，请计算不超过N的满足猜想的素数对的个数。 输入格式：每个测试输入包含1个测试用例，给出正整数N。 输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。 输入样例： 20 输出样例： 4 ### 分析（伪代码和知识点） 1.该题的意思是求出n之前的素数对的个数（n是输入的数且素数对的差为2）根据题意可知该题需要一个判断素数的函数，然后由主函数进行素数对个数的计算。所以大体框架如下： 　　　　int isprime(){ 　　　　　　//求素数函数 　　　　} 　　　　int main(){ 　　　　　　//输入 　　　　　　//计算个数 　　　　　　//输出 　　　　} 2.输入： 　　　　int n; 　　　　scanf("%d"&n); 3.判断是否为素数 　　　　int isprime(int n){ 　　　　　　//通过一个for循环判断n是否为素数(遍历n之前的数) 　　　　for(int i=0;i<n;i++){ 　　　　if(n%i==0){return 0}; 　　　　} 　　　　return 1;//如果返回1则为素数 　　　　} 4.计算个数(通过一个for循环计算) 　　　　int i,k; 　　　　for(i=3;i<=n-2;i++){ 　　　　if(isprime(i) && isprime(i+2)){ 　　　　　　　　k++; 　　　　　　 　　　　　　　//通过比较从i到n-2中有多少对差为2的素数，相应 　　　　　　　　　　的计数器加1 　　　　　　　} 　　　　} 5.输出：输出要求的个数,该个数是由通过一个计数器来实现的. 　　　　printf("%d",k); ### 代码1 ``` #include <stdio.h> #include <math.h> int sushu(int x){ int t,j; t=(int)sqrt((double)x); for(j=2;j<=t;j++){ if(x%j==0){ return 0; } } if(j>t){ return 1; } } int main(void){ int i,n,k=0; scanf("%d",&n); for(i=3;i<=n-2;i++){ if(sushu(i)&&sushu(i+2)){ k++; } } printf("%d",k); } ``` ###代码2 ~~~ #include <stdio.h> #include <math.h> int isPrime(int n) { int i; if (n == 1) return 0; else if (n == 2) return 1; else if (n % 2 == 0) return 0; else { for(i=3;i*i<=n;i++){ if( n % i==0) return 0; } return 1; } } int main(void) { int n; scanf("%d", &n); int pair_cnt = 0; int i; for (i = 2; i < n; i++) { if (isPrime(i) && isPrime(i + 2) && (i + 2) <= n){ // printf("%d,%d ",i,i+2); pair_cnt++; } } printf("%d\n", pair_cnt); return 0; } ~~~  ###代码3 ~~~ #include <stdio.h> #include <math.h> int isPrime(int n) { if (n == 1) return 0; else if (n == 2 || n == 3) return 1; else if (n % 2 == 0) return 0; else { int i, end; end = (int)sqrt(n) + 1; for (i = 3; i < end; i += 2) { if (n % i == 0) return 0; } return 1; } } int main(void) { int n; scanf("%d", &n); int pair_cnt = 0; int i; for (i = 2; i < n; i++) { if (isPrime(i) && isPrime(i + 2) && (i + 2) <= n){ // printf("%d,%d ",i,i+2); pair_cnt++; } } printf("%d\n", pair_cnt); return 0; } ~~~