素数对猜想

• • 素数对猜想
  • • 输入格式:
    • 输出格式:
    • 输入样例:
    • 输出样例:
    • 思路分析
    • 代码
    • 我的解法
    • • • 初代码
        • 我更改后的最终代码
  • 模板
  • • • 求出 2 ~ n 以内的素数

让我们定义 dn (n为下标) 为：dn=pn+1−pn，其中 pi 是第 i 个素数。显然有 d1=1，且对于 n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

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

输入在一行给出正整数N。

在一行中输出不超过N的满足猜想的素数对的个数。

20
结尾无空行

4
结尾无空行

1.接收数据 int n
2.求出 2 ~ n 以内的素数
3.在范围内筛选

2.3.也可以同时进行

#include 
#include 
int main(){
    
    //1.接收数据 int n
    int n;
    scanf("%d",&n);
    
    //2.求出 2 ~ n 以内的素数
 	int i, j, k = 0;
    int a[n];
    for(i = 2; i <= n; i++)
    {
        for(j = 2; j <= sqrt(i); j++){
            if(i % j == 0)
                break;
        }
        if(j > sqrt(i)){
            a[k] = i;
            k++; 
        }
    }
    
    //3.在范围内筛选
    int count = 0;
    for(i = 1; i <= k; i++)
    {
		if(a[i] - a[i-1] == 2){
			count++;
        }
    }
    printf("%d", count);
    return 0;
}

#include 
int main(){
    
    //思路分析
    
    int n, count = 0, k = 1;
    scanf("%d",&n);
    int suShu[n];
    suShu[0] = 2;
    if(n < 5){
        printf("%d",0);
    }else{
        for(int i = 2; i <= n; i++){
            for(int j = 2; j < i; j++){
                if(i % j == 0){
                    break;
                }
                if(j == i - 1){
                    suShu[k] = i;
                    if(suShu[k] - suShu[k-1] == 2){
                    	count++;
					}
					k++;
                }
            }
        }
        printf("%d",count);
    }  
}

#include 
#include  
int main(){
    //思路分析
    
    int n, count = 0, k = 1;
    scanf("%d",&n);
    int suShu[n];
    suShu[0] = 2;
    if(n < 5){
        printf("%d",0);
    }else{
        for(int i = 2; i <= n; i++){
        	int j;
            for(j = 2; j <= sqrt(i); j++){
                if(i % j == 0){
                    break;
                }
            }
            if(j > sqrt(i)){
                suShu[k] = i;
                if(suShu[k] - suShu[k-1] == 2){
                    count++;
				}
				k++;
                }
        }
        printf("%d",count);
    }  
}

判断方法可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~ √m 之间的每一个整数去除就可以了。如果 m 不能被 2 ~ √m 间任一整数整除，m 必定是素数。

因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于 √m ,另一个大于或等于 √m )。例如 16 能被 2、4、8 整除，16 = 2 * 8，2 小于 4，8 大于 4，16 = 4 * 4，4=√16，因此只需判定在 2 ~ 4 之间有无因子即可。

int i, j, k = 0;
int a[n];
for(i = 2; i <= n; i++){
    for(j = 2; j <= sqrt(i); j++){
    	if(i % j == 0)
        	break;
    }
    if(j > sqrt(i)){
     	a[k] = i;
      	k++; 
    }
}