Prime 篩子

Eratosthenes 的篩子產生從 2 到給定數 n 的所有素數。

1. 假設所有數字（從 2 到 n ）都是素數。
2. 然後取第一個素數並刪除它的所有倍數。
3. 迭代下一個素數的第 2 步。繼續，直到標記為 n 的所有數字。

虛擬碼：

Input: integer n > 1
 
Let A be an array of Boolean values, indexed by integers 1 to n,
initially all set to true.
 
for i = 2, 3, 4, ..., not exceeding sqrt(n):
    if A[i] is true:
        for j = 2i, 3i, 4i, 5i, ..., not exceeding n :
            A[j] := false
 
Output: all i such that A[i] is true.

C 程式碼 ：

void PrimeSieve(int n)
{
    int *prime;
    prime = malloc(n * sizeof(int));
        int i;
        for (i = 2; i <= n; i++)
            prime[i] = 1;    
    
       
    int p;
    for (p = 2; p * p <= n; p++)
    {    
        if (prime[p] == 1) // a Prime found
        {
            // mark all multiples of p as not prime.
            for (int i = p * 2; i <= n; i += p)
                prime[i] = 0;
        }
    }
 
    // print prime numbers
    for (p = 2; p <= n; p++)
        if (prime[p] == 1)
            printf("%d ", p);
}