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年历史的Eratosthenes筛子：

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

如果你想了解更多，我谦虚地推荐我博客上的散文。

Answer 2

有一个著名的素数定理。它说明了

π(n)≈n/ln(n)

但是有一些特定的算法来计算这个函数。点击链接：PNT

Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method