试除法求最小N个素数之二

Trial division

试除法求最小N个素数是一个经典的算法。

这个算法不同于前一个版本《试除法求最小N个素数》的方法，也是一个比较快速的方法。

这个算法考虑以下两点：

1.偶数中只有2是素数，其他素数是奇数；

2.试除法中，对于数n，只需要对使用小于sqrt(n)的素数试除即可，n只需要用3，5，7，...，进行试探。并且只需要用已知的素数作为除数即可。

程序中，利用已经知道的素数去试除，处理速度上自然就快。开始时，将2和3放入已经求得的素数数组中是必要的。函数isprime()只需要考虑对奇数进行判定即可，所以用从3开始的奇素数试除。

程序如下：

/* 试除法计算最小的N个素数 */

#include <stdio.h>
#include <math.h>

#define N 132

#define TRUE 1
#define FALSE 0

typedef unsigned long long ULL;

ULL prime[N+1] = {2, 3};

int isprime(ULL prime[], int n)
{
    ULL end = (ULL)sqrt(n);
    int i;
    for(i=1; prime[i]<=end; i++)
        if(n % prime[i] == 0)
            return FALSE;
    return TRUE;
}

void genprime(ULL prime[], int n)
{
    int k = 2;
    for(int i=5; k<n; i+=2)
        if(isprime(prime, i))
            prime[k++] = i;
}

int main(void)
{
    genprime(prime, N);

    for(int i=0; i<N; i++)
        printf("%lld
", prime[i]);

    return 0;
}

计算结果如下：