目前已知的一种最快速的求素数的算法就是Sieve of Atkin 算法！

前m个素数是指从2开始的m个素数，比如前3个素数是：2，3，5；前10个素数是：2，3，5，7，11，13，17，19，23，29。

要找出前m个素数，很容易想到的算法是从2开始依次判断每一个整数是否是素数，直到找到m个素数。首先涉及到判断一个给定的数n是否为素数，其最简单的算法是，依次判断所有大于1且小于n的整数中是否存在能被n整除的数i，若存在则n不是素数，不存在则n为素数。代码实现如下：
//算法1
int isPrimeNumber(long n)
{
	for(int i = 2; i < n; i++)
	{
		if(n % i == 0)
			return 0;  //n不是素数
	}
	return 1;  //n是素数
}

该算法最简单明了，但有很大的缺点，判断次数多，冗余操作多，时间复杂度为O(n)。
实际上，算法1中n除以i得到的商小于i后，依然没有出现整除，则之后的整数已无需判断，就可以判定n为素数。因此对该算法进行一个简单的优化，将for(int i = 2; i < n; i++)改为for(int i = 2; i <= n/i; i++)，所得到的新算法记为算法2，其冗余的判断整除的操作减少很多，时间复杂度减少到O(√n)。
但是该算法依然存在冗余判断整除操作，例如n已经无法整除2和3，那么显然也无法整除6，但该算法依然会对6进行整除判断。若将算法中的这类冗余操作完全去除，则运算速度将会进一步加快。那么有没有一种算法能做到没有冗余呢？
我们已知在数学上判断素数的方法：试除法，用从2开始的各个质数依次去除n，如果存在某一个质数整除，那么n不是质数；若不能整除，一直尝试到商小于除数，那么n是一个质数。这个方法没有冗余判断操作。
在打印前m个素数的算法中，可以使用一个数组来记录已经找到的质数。前几个素数已经为人们所熟知，无需再进行计算，因此可以把它们提前记录在这个数组中，比如可以将前8个素数2，3，5，7，11，13，17，19预先填入数组，后面找到的其他素数依次填入其中。将该算法记为算法3。以算法3为基础，得到打印前m个素数的C代码如下：
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

#define MAX_SIZE  10000   //最多记录的素数个数

long primeNumberArray[MAX_SIZE] = {2, 3, 5, 7, 11, 13, 17, 19}; 
//初始化数组，填入前8个熟知的素数
int  currentPrimeNumber = 8;  //记录数组中已有的素数个数

//判定一个给定的数n是否为素数，若是返回1，不是返回0，出错返回-1
int isPrimeNumber(long n)
{
	long index = 0;
    for ( index = 0; index < currentPrimeNumber; index++)
	{
		if ( 0 == n % primeNumberArray[index] )
            return 0;  //n不是素数
		else if ( primeNumberArray[index] > (n/primeNumberArray[index]))	
		    return 1;  //n是素数
	} 
    return -1;
}

int main()
{
    int m;
    int result = 0, i = 0;
    long currentNumber = 21; //要判断的数，数组记录到19，从21开始

	printf("number of prime numbers to print: ");
	scanf("%d", &m);
	printf("\n");
   
    while (currentPrimeNumber < m)
	{
		result = isPrimeNumber(currentNumber);
		if (1 == result) //找到一个新的素数，记录到数组中
        {
			primeNumberArray[currentPrimeNumber] = currentNumber;
            currentPrimeNumber++;
		}
        else if (-1 == result)
        {
			printf("Fatal error occur!\n");
		}
		currentNumber += 2; //大于2的偶数均为和数，因此递增2
	}
    
    //打印前m个素数
	printf("Index     Prime Number\n");
    for (i = 0; i < m; i++)
		printf("%10d %ld\n",i + 1, primeNumberArray[i]);

	return 0;
}


为了验证这个无冗余算法的性能优势，我们在该程序中的while循环前后记录时间点，用以计算该程序耗时，以微秒为单位，更改后的main函数如下：
int main()
{
    int m;
    int result = 0, i = 0;
    long currentNumber = 21;
	struct timeval start, end;
	struct timezone tz;
    long timeelapse = 0;

	printf("number of prime numbers to print: ");
	scanf("%d", &m);
	printf("\n");

    gettimeofday(&start, &tz);  //开始计时
    while (currentPrimeNumber < m)
	{
		result = isPrimeNumber(currentNumber);
		if (1 == result)
        {
			primeNumberArray[currentPrimeNumber] = currentNumber;
            currentPrimeNumber++;
		}
        else if (-1 == result)
        {
			printf("Fatal error occur!\n");
		}
		currentNumber += 2;
	}
    gettimeofday(&end, &tz);  //结束计时
    
	printf("Index     Prime Number\n");
    for (i = 0; i < m; i++)
    {
		printf("%10d %ld\n",i + 1, primeNumberArray[i]);
	}	
	
	//计算并打印耗时，单位微秒
    timeelapse = (end.tv_sec - start.tv_sec)*1000*1000 + end.tv_usec - start.tv_usec;
    printf("timeelaspe = %ld\n", timeelapse);
    
	return 0;
}


在Ubuntu虚拟机上将函数isPrimeNumber(long n)依次替换为算法1，2和3，在打印前1000个、前5000个和前10000个素数时重复运行5次，观测时间耗费（微秒）取平均值，统计得到如下表格：




打印个数
1000
5000
10000




算法1
40589
1155341
4978551


算法2
1583
23223
71557


算法3
902
7133
17284


根据统计结果可以明显看出，算法1耗时最长，没有实用性，算法3在所有情况下的用时最少，效率最高。当打印素数的个数逐渐增加时，算法3相对于算法2的优势越来越大。但是算法3的使用也有一定局限性，其能判定的最大整数不能超过数组中最后一个素数的平方，并且其需要保存所得到的素数列表，因此比前两个算法占用更多的内存空间。

参见英文答案 >
Fastest primality test                                    3个
我正在编写一个方法来检测BigInteger是否为素数.我使用以下代码/算法来检查给定数字是否为素数.但这是非常缓慢的,如果一个数字可以说长10个数字需要很长时间.
public boolean returnPrime(BigInteger testNumber){
int divisorCounter=1;
BigInteger index,i ;
for ( index= new BigInteger("2"); index.compareTo(testNumber) !=1; index=index.add(new BigInteger("1"))){
System.out.println(index);
for(i= new BigInteger("2"); i.compareTo(index) != 1; i=i.add(new BigInteger("1"))){
if((testNumber.mod(i).equals(BigInteger.ZERO) )){
divisorCounter++;
}
if(divisorCounter>2){
return false;
}
}
}
return true;
}
是否有更好的算法可以使用BigInteger素数？我在Stackoverflow中找不到与此相关的问题.如果您遇到过这样的问题请告诉我,或者如果您对如何解决有任何想法,那么您的想法将受到高度赞赏.

填坑了。
之前说到，2 和 3之后，所有质数都必须满足6 n ± 1这个条件。所以利用这原理，可以提升三倍性能。这公式怎么来的呢？
首先我们知道，2以后的质数都必须是奇数，公式表达就是2n + 1，当然用2n - 1也行。
我们要把能整除3的过滤掉。即 2n + 1 不能整除3。我们做适当转换：
2n + 1 => 3n - n + 1
可见，我们只要确保1 - n不能整除3就可以。
令 n = 3 m + x，则有2 * (3m + x) + 1 => 6m + 2x + 1 ，x 的取值范围为 0 和 2。
所以得到，6m + 1 或者 6m + 5，其中6m + 5 等同于 6m - 1，只是m取值范围不同。
证明完毕。
同样，当我们有了6n ± 1之后，怎么去除 5和7 的倍数呢？刚好就这么巧：
6n ± 1 => 5n + n  ± 1
6n ± 1 => 7n - n ± 1
懂了吧，剩下展开就行了。实测下，把3倍数过滤掉，用欧拉确实获得巨大的性能提升。
再把5倍数过滤掉，还能提升一点。到再过滤7倍数的时候，优势就有点看不到了，原因是，5级过滤到7级过滤，计算总量是从8/30 降到 48/210，节约率相比原始来说才3.8%，收益不多。
说好的代码呢？呃，上吧，F# 的代码。
let getPrimers maxValue =
let table = [|0uy; 2uy; 6uy; 8uy; 12uy; 18uy; 20uy; 26uy; 30uy; 32uy; 36uy; 42uy;
48uy; 50uy; 56uy; 60uy; 62uy; 68uy; 72uy; 78uy; 86uy; 90uy; 92uy;
96uy; 98uy; 102uy; 110uy; 116uy; 120uy; 126uy; 128uy; 132uy; 138uy;
140uy; 146uy; 152uy; 156uy; 158uy; 162uy; 168uy; 170uy; 176uy; 180uy;
182uy; 186uy; 188uy; 198uy; 200uy|]
let check = Array.zeroCreate (maxValue + 1)
let prime = Array.zeroCreate (maxValue / 210 * 48 + 48)
prime.[0] 
prime.[1] 
prime.[2] 
prime.[3] 
let rec loop n count step =
let i = n + int32 table.[step]
if i <= maxValue then
let count =
if not check.[i] then
prime.[count] 
count + 1
else
count
let rec loopPrime j =
if j < count then
let comp = i * prime.[j]
if comp <= maxValue then
check.[comp]  0 then
loopPrime (j + 1)
loopPrime 4  // 把0 改为 4，这一步很重要，因为原理上杜绝了 2357倍数的检查，                         // 所以直接不用标注, 2000万数据测试下，节约了1/4时间            if step + 1 = table.Length then
loop (n + 210) count 0
else
loop n count (step + 1)
loop 11 4 0
===================================
看完一圈，没有一个好打的。
就抄个公式出来了事。那些所谓擅长数学的，怎么不知道2和3之后，所有质数都必须满足6 n ± 1这个条件？因为只有6 n ± 1才能避开2和3的倍数。 欧拉筛法改一下，速度一下子提到3倍了。即使你真的不懂，也该知道2之后，所有质数都是奇数吧?也能从原来提升两倍速度了。如果你想，数组也可以趁机把数组开小一点。优化都没尝试过就说这个算法内存占用什么的。。。。。
不才还有个「210里面中检测48个可能位置的」，也就是说，从开始就排除2、3、5、7的倍数。大概能提升到4倍(略低于4倍)。原理和代码稍晚放出。