c - 查找不超过给定值 n 的素数的优化方法

Question

我通过使用此函数对每个值 k 检查从 k=3 到 n(给定上限值)来完成此操作。我如何优化它以获取数组中直到 n 的所有素数，而不需要检查每个数字 k？

int primeCheck(long long int k) {
    int j;
    int isPrime = 1;
    int sr = (int)sqrt(k);
    for (j = 2; j <= sr; j++) {
        if (k % j == 0) {
            //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisible
            isPrime = 0; // this number is not prime, cos num can be divided by num2
            break;
        }
    }
    if (isPrime) {
        return isPrime; // reset the check parameter
    } else {
        return 0; // reset the check parameter
    }
    return 0;
}

Answer 1

试试埃拉托色尼筛法。该算法通过消除从 2 到 n 的素数的所有因子来工作。

int main() {
    int n;
    scanf("%d", &n);
    int prime[n+1];
    for(int i = 0; i < n+1; i++)
        prime[i] = 0;

    for(int i = 2; i <= sqrt(n+1); i++) {
        if(prime[i] == 0) {
            for(int j = i*i; j <= n; j += i)
                prime[j] = 1;
        }
    }

    int prime_list[n], size = 0;
    for(int i = 2; i <= n; i++) {
        if(prime[i] == 0)
            prime_list[size++] = i;
    }
}

例如让数字最初是:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

• 删除 2 的所有倍数(2 除外)我们得到:

2 3 5 7 9 11 13 15 17 19 21 23 25 27 29

• 删除 3 的所有倍数(3 除外)，我们得到:

2 3 5 7 11 13 17 19 23 25 29

• 删除 5 的所有倍数(5 除外)，我们得到:

2 3 7 11 13 17 19 23 29

现在，将不再有删除，并且在对每个剩余素数进行多次迭代后，这将是我们的最终列表。

prime[i] for i = {2, 3, 7, 11, 13, 17, 19, 23, 29}。我们会将所有这些索引附加到另一个 prime_list vector ，如代码中所做的那样。该 vector 将给出 [2, n] 中的所有质数。