C程序优化/速度提升

Question

作为初学者，我编写了一个程序来查找不大于输入自然数 (x) 的素数 (prime) 的数量。该程序运行良好(我认为)，但我想让它运行得更快(对于更高的数字)。有可能吗？如果有，如何实现？

#include <stdio.h>

int main() {
    int x, i, j, flag = 1, prime = 0 ;

    scanf("%d", &x);
    for (i = 2; i <= x; i++) {
        j = 2;
        while (flag == 1 && j < i/2 + 1 ) {
            if (i % j == 0) {
                flag = 0;
            }
            j++;
        }
        if (flag == 1) {
            prime++;
        }
        flag = 1;
    }
    printf("%d\n", prime);
    return 0;
}

Answer 1

你的算法进行试除法，这很慢。更好的算法是具有 2000 年历史的埃拉托色尼筛法:

function primes(n):
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p # prime
            for i from p*p to n step p
                sieve[i] := False

我会把它翻译成C。如果你想了解更多，我谦虚地推荐这篇文章Programming with Prime Numbers在我的博客上。