算法面试题：求素数

问题： 编写一个程序，求前 N 个素数。例如，如果 N 为 100，则找到前 100 个素数。

分析：素数（或质数）是指大于1且不能被除1和该数本身以外的其他自然数整除的自然数，如2、3、5... 。最基本的想法是评估从 1 到 N 的每个数字，并输出它是否是素数。改进的方法是不需要考虑从1到N的所有数字，因为除2之外的偶数肯定不是素数，而奇数可能是也可能不是素数。那么我们可以跳过2和3的倍数，即对于6n, 6n+1, 6n+2, 6n+3, 6n+4, 6n+5，计算就足够了 6n+ 只关心 1 和 6n+5 是否是质数。

判断一个数 m 是否为质数的最基本方法是将 m 除以 2 和 m-1。如果有一个数能整除m，则m不是素数。判断m是否素数的判断还可以进一步改进。不需要将 m 除以 2 到 m-1 之间的所有数字，只需将 m 除以 2 到 m 的根之间的数字即可。例如，要除 m，请使用 2, 3, 4 , 5... 根 m。事实上，这仍然是一种浪费，因为如果2不可整除，则2的倍数也不可整除；同样，如果3不可整除，则3的倍数也不可整除。因此，只能使用 2 到 m 的平方根之间且小于 m 的平方根的素数。只需将其删除即可。

解法：可以预先求出2、3、5为素数，然后跳过2、3的倍数，从7开始，然后判断11，再判断13，再判断17……规则是从5开始加2，然后是4，然后是2，然后是4。如下图所示重复，你只需判断数字7, 11, 13, 17, 19, 23, 25, 29.. .。

判断是否素数采用了一种改进的方案，即2与m的根之间的数除以m，需要注意的是，不能直接用m的根的符号来判断，因为对于某些数字，比如是121的根号，可以是10.999999，所以最好用代码所示的乘法来判断。

/**
 * 找出前N个质数, N > 3
 */
int primeGeneration(int n)
{
    int *prime = (int *)malloc(sizeof(int) * n);
    int gap = 2;            
    int count = 3;
    int maybePrime = 5;
    int i, isPrime;

    /* 注意：2, 3, 5 是质数 */
    prime[0] = 2;
    prime[1] = 3;
    prime[2] = 5;

    while (count < n)  {
         maybePrime += gap;
         gap = 6 - gap;
         isPrime = 1; 
         for (i = 2; prime[i]*prime[i] <= maybePrime && isPrime; i++)
              if (maybePrime % prime[i] == 0)
                   isPrime = 0;

         if (isPrime)
              prime[count++] = maybePrime;
    }

    printf("\nFirst %d Prime Numbers are :\n", count);

    for (i = 0; i < count; i++) {
         if (i % 10 == 0) printf("\n");
         printf("%5d", prime[i]);
    }
    printf("\n");
    return 0;
}

作者：ssjhust
来源：掘金