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);
}