算法面试题：找质数问题

题： 写一个程序，找出前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是否是质数，最基本的方法就是对 2 到 m-1 之间的数整除 m，如果有一个数能够整除 m，则 m 就不是质数。判断 m 是否是质数还可以进一步改进，不需要对 2 到 m-1 之间的数全部整除 m，只需要对 2 到 根号m 之间的数整除m就可以。如用 2，3，4，5...根号m 整除 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;
}