1007. 素数对猜想 (20)

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

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

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

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

输入样例：

20

输出样例：

4

思路：创建一个10000的数组， 查找 0~N 的素数并存储到数组中， 然后在数组中查找素数对，并记录个数；

C语言：

#include <stdio.h>
int is_prime(int n);

const int N = 100000;
int main(void)
{
    int prime[N];
    int count = 0;
    int n, flag;
    scanf("%d", &n);
    
    // 找素数  
    int i;
    for (i=2; i<=n; i++){
        if (is_prime(i)){
            prime[count++] = i;
            //printf("%d\n", i);
        }
    }
    
    //  查找素数对对数 
    int sum = 0;
    for (i=0; i<count-1; i++){
        if (prime[i+1] - prime[i] == 2){
            sum++;
        }
    }
    printf("%d", sum);
    
    return 0;
}

// 判断 n 是否为素数 
int is_prime(int n)
{
    int j;
    int flag = 1;
    for (j=2; j<n/2+1; j++){
        if (n%j == 0){
            flag = 0;
            break;
        }
    }
    
    return flag;
}

最后一个测试没有通过，超时了，看来要优化算法。

1107.jpg

用另一种方法重写了：

#include <stdio.h>

int main(void)
{
    int n;
    scanf("%d", &n);
    int arr[n+1];

    // 初始化为 1
    int i, j;
    for (i=2; i<n+1; i++){
        arr[i] = 1;
    }
    
    // 将质数的倍数标记为非质素
    for (i=2; i<n+1; i++){
        if (arr[i] == 1){
            for (j=2; i*j <= n; j++){
                arr[i*j] = 0;
            }
        }
    }
    
    int count = 0;
    int temp = 2;   // 记录当前素数，前面的那位素数。
    int num;
    for (i=3; i<n+1; i++){
        if (arr[i] == 1){
            if (i - temp == 2){
                count++;
            }
            temp = i;
        }
    }
    printf("%d", count);
    
    return 0;
}

构造素数表.jpg