时间戳

首页 > 解决方案 > 找到两个连续的素数，使得它们之间的间隔大于或等于 N

c - 找到两个连续的素数，使得它们之间的间隔大于或等于 N

问题描述

我正在编写一个程序来读取整数 n (0 < n <= 150) 并找到最小的素数 p 和连续素数 q，使得 q - p >= n。

我的代码有效，但对于较大的 n，它运行大约 10 秒。

#include <stdio.h>
#include <stdlib.h>

int isPrimeRecursive(int x, int i){
    if (x <= 2){
        return (x == 2 ? 1:0);
    }
    if (x % i == 0){
        return 0;
    }
    
    if (i * i > x){
        return 1;
    }
    return isPrimeRecursive(x, i+1);
}

int findSuccessivePrime(int x){
    while (1){
        x++;
        if (isPrimeRecursive(x, 2)){
            return x;
        }
    }
    return 0;
}

int findGoodGap(int n, int *arr){
    int prime = findSuccessivePrime(n*n);
    
    while (1){
        int gap;
        int succPrime;
        succPrime = findSuccessivePrime(prime);
        gap = succPrime - prime;
        if (gap >= n){
            arr[0] = succPrime;
            arr[1] = prime;
            return gap;
        }
        prime = succPrime;
    }
    return 0;
}

int main(int argc, char *argv[]){
    int n;
    int arr[2];
    scanf("%d", &n);
    int goodGap;
    goodGap = findGoodGap(n, arr);
    
    printf("%d-%d=%d\n", arr[0], arr[1], goodGap);
    
    return 0;
}

如何让程序更有效率？我只能使用 stdio.h 和 stdlib.h。

标签： cprimes

解决方案

该算法非常低效。你一遍又一遍地重新计算相同的东西。你可以这样做：

int n;
// Input n somehow
int *p = malloc(n * sizeof *p);

for(int i=0; i<n; i++) p[i] = 1; // Start with assumption that all numbers are primes

p[0]=p[1]=0; // 0 and 1 are not primes

for(int i=2; i<n; i++) 
    for(int j=i*2; j<n; j+=i) p[j] = 0;

现在，p[i]可以将其视为判断是否i是素数的布尔值。

以上可以进一步优化。例如，当您已经删除了所有可被 2 整除的数字时，删除所有可被 4 整除的数字是毫无意义的。这是一个非常简单的 mod：

for(int i=2; i<n; i++) {
    while(i<n && !p[i]) i++; // Fast forward to next prime

    for(int j=i*2; j<n; j+=i) p[j] = 0;
}

正如 Yom B 在评论中提到的，这是一种记忆模式，您可以在其中存储结果以备后用，这样我们就不必重新计算所有内容。但是动态编程更进一步，这基本上意味着使用记忆作为算法本身的一部分。

在 C64 演示场景中大量使用的纯记忆的一个示例是预先计算三角函数的值表。甚至使用简单的乘法表，因为 C64 处理器的乘法比简单的查找要慢得多。一个缺点是更高的内存使用率，这是旧机器上的一个大问题。

推荐阅读