找出給定範圍內的質數 -- Sieve of Eratosthenes

Sieve of Eratosthenes是一種找出給定範圍內的演算法，從該範圍內最小質數開始，逐步刪除該質數的乘積，圖形化表達如下


C 程式如下

bool prime[20000000];

void eratosthenes()
{
    for (int i=0; i < 20000000; i++)
        prime[i] = true;

    prime[0] = false;
    prime[1] = false;

    for (int i=2; i < 20000000; i++)
        if (prime[i])
            for (int j=i*i; j < 20000000; j+=i)
                prime[j] = false;
}

用來實做質數表非常有用，在這邊也有提到更多細節與加速該演算法的方法