PAT 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的满足猜想的素数对的个数。

输入样例：

输出样例：

如果运行超时，那可能是判断素数时没开根号。

因为任何一个数的因数是成对出现的，而且分布在根号的两侧。如果小于开根号的一侧没有，那么另一侧也一定没有。就一定是素数了。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 int main(){
 5     int number;
 6     int temp = 2;
 7     int sum = 0;
 8     int j;
 9     scanf("%d",&number);
10     for(int i=2;i<=number;i++){
11         int temp1 = (int)sqrt(i);
12         for(j=2;j<=(int)sqrt(i);j++){
13             if(i%j==0)
14                 break;
15         }
16         if(j>(int)sqrt(i)){
17             if(i-temp==2){
18                 sum++;
19             }
20             temp = i;
21         }
22     }
23     printf("%d",sum);
24 }
25