如何编程最快速度求出两百万以内素数个数（不限语言和算法）？

程序员文章站 2024-01-26 13:10:58

...

回复内容：

x贴一个优化得比较过分的线性筛。用位模式保存状态，直接绕过2和3的倍数。

#include 
#include 
#include 
#include 

#define PRIME_LIM 10000000
#define N 100000000

int primes[PRIME_LIM] = {0};
int flags[N/96 + 1] = {0};

int get_prime()
{
    int nu = 5, to = 0;
    primes[0] = 2;
    primes[1] = 2, primes[2] = 3;
    for(int i = 0; nu  N; i++) {
        if(!(flags[i>>5]&(1(i&31)))) primes[++primes[0]] = nu;
        for(int j = 3; j  primes[0] && primes[j] * nu  N; j++) {
            to = (nu * primes[j] - 5) >> 1;
            to -= to/3;
            flags[to>>5] |= 1(to&31);
            if(!(nu % primes[j])) break;
        }
        nu += 2 + ((i&1)  1);
    }
    return primes[0];
}

int main()
{
    clock_t t = clock();
    printf("%d\n", get_prime());
    printf("Time:%f\n", 1.0 * (clock() - t) / CLOCKS_PER_SEC);
    for(int i = 1; primes[i]  100; i++) {
      printf("%d\n", primes[i]);
    }
    return 0;
}

【多种方法比较，长文慎入】

看到各位大神用各种语言写的代码，我这个外行人也跃跃欲试了。
鉴于大家已经给出了C，C++，Python，Mathmatica等的实现过程，那我就用Java吧。

我不会流氓地直接用各种Prime函数（那样对问题讨论毫无意义），还是给出完整实现过程吧。
算法一般，还有待改进，欢迎各位大神指正：

我用的是筛法，稍稍做了优化（把偶数单独列出来筛），代码如下：

1、初始版代码：

class Prime{	
	public static int calculateNumber(int Nmax){
		boolean[] isPrime=new boolean[Nmax+1];		
		for(int i=3;iNmax;i+=2)
			isPrime[i]=true;
		isPrime[2]=true;
		for(int i=3;iMath.sqrt(Nmax);i+=2){
			if(isPrime[i]==true){
				for(int j=i*i;jNmax;j+=2*i)
					isPrime[j]=false;
			}
		}
		int primeNum=0;
		for(int i=1;iNmax;i++){
			if(isPrime[i]==true)
				primeNum++;
		}
		return primeNum;
	}				
	public static void main(String[] args){
		final int Nmax=2000000;
		double startTime=System.currentTimeMillis();
		int primeNum=Prime.calculateNumber(Nmax);
		double timeSpent=(System.currentTimeMillis()-startTime)/1000;
		System.out.println("The prime numbers from 1 to "+Nmax+" is "+primeNum);
		System.out.println("Time spent : "+timeSpent+" s");
	}
}

如果题主希望得到的答案仅限于筛法，那基本上线性筛从复杂度上已经是最优的了，只剩下各种优化了。特别是如果要死扣最后那么点性能，就必然是面向体系结构的优化了，比如多线程优化、根据intel的体系结构如何选择各类指令的分布、用类似prefetch之类的指令降低存储器访问延迟等等。

至于算法层面，从标题来看只是求质数个数，而并不需要枚举所有质数。于是存在比线性更优的算法，可以参考：素数计数函数。其时间复杂度为O(x^(2/3)/log(x))，空间复杂度为O(x^(1/3)log(x)^2)
具体代码实现可以围观：kimwalisch/primecount · GitHub 。

当然最后运行时间对于两百万这个“小”数据基本是可以忽略不计的（

Mathematica可以在0.012001秒解出来。 http://quartergeek.com/sieve-prime-in-linear-time/
线性筛法我来终结此问题。
计算素数个数被数学家和ACMer玩烂了，没啥优化的空间了。
用C语言，计算200万以内素数个数，100次实验取平均
用埃氏筛法，0.035620 seconds
用欧拉筛法，0.025630 seconds
计算1亿以内素数个数，10次实验取平均
用埃氏筛法，2.890600 seconds
用欧拉筛法，1.473400 seconds
运行机器：32位XP

#include 
#include 
#include 
#include 
const int N = 2000000;
bool b[N+1];
int c[N+1];
void Era_select(){ // Eratosthenes
	memset(b, 0, N+1);
	int q = (int)sqrt(N);
	int i, j, cnt = 0;
	for ( i=2; iq; ++i ){
		if ( ! b[i] ){
			for ( j=i1; jN; j+=i ){
				b[j] = true;
			}
		}
	}
	for ( i=2; iN; ++i ){
		if ( ! b[i] ){
			++cnt;
		}
	}
	//printf("%d\n", cnt);
}
void Euler_select(){
	memset(b, 0, N+1);
	int i, j, cnt = 0, t;
	for ( i=2; iN; ++i ){
		if ( ! b[i] ){
			c[cnt++] = i;
		}
		for ( j=0; jcnt; ++j ){
			t = i*c[j];
			if ( t > N ){
				break;
			}
			b[t] = true;
			if ( i%c[j] == 0 ){
				break;
			}
		}
	}
	//printf("%d\n", cnt);
}
int main(){
	int i, num=100;
	clock_t start;
	start = clock();
	for ( i=0; inum; ++i ){
		Era_select();
	}
	printf("%lf seconds\n", (double)(clock()-start) / CLOCKS_PER_SEC / num);
	start = clock();
	for ( i=0; inum; ++i ){
		Euler_select();
	}
	printf("%lf seconds\n", (double)(clock()-start) / CLOCKS_PER_SEC / num);
	return 0;
}

*上有个关于用python求解最快算法的讨论（optimization），如果用纯python语言的话，最快的算法是下面这个：

def rwh_primes2(n = 10**6):
    # http://*.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a list of primes, 2 
    correction = (n%6>1)
    n = {0:n,1:n-1,2:n+4,3:n+3,4:n+2,5:n+1}[n%6]
    sieve = [True] * (n/3)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
      if sieve[i]:
        k=3*i+1|1
        sieve[      ((k*k)/3)      ::2*k]=[False]*((n/6-(k*k)/6-1)/k+1)
        sieve[(k*k+4*k-2*k*(i&1))/3::2*k]=[False]*((n/6-(k*k+4*k-2*k*(i&1))/6-1)/k+1)
    return [2,3] + [3*i+1|1 for i in xrange(1,n/3-correction) if sieve[i]]

很多人说我是喷子，我不同意

对于治病救人，我有时候有不同的理解，这很正常。
看到有人在吃屎，安全的做法是告诉他慢慢吃别噎着，加点油盐酱醋味精啥的，再端碗鸡汤，然后皆大欢喜，大家都很高兴。
虽然我倡导diversity，但我对这种行为异常鄙夷，我认为，你他妈应该立即打断啊。。。（当然，我知道有人是嗜粪的，所以因为我每次都打断所以有时候我也会犯错，但这种情况还是罕见的）

如果不是我必须表现得礼貌，我会说你写的这些东西还不如一坨屎

这是一段根本没法运行的代码，whese is is_prime()???
100000用1e6，我不知道你是什么心态？如果装逼，则可以叉出去了，如果不知道可以直接用200000.....尼玛32位数4294967296是常识吧？更应该叉出去了
乱取名字，竟敢覆盖list，真坑爹
好好的math.sqrt不用，用什么**0.5，什么心态
你那么喜欢所谓“黑科技”优化，为啥不用xrange？
乱用列表推倒，列表没推倒，你自己先倒了
你那么喜欢省代码行数讨厌回车，我推荐你用c语言，用那个可以写成一行
哪有这样写python的？
你觉得跑了21秒的程序有必要写清楚型号配置吗？
如果不是我必须表现得礼貌，我会问你觉得这种垃圾有必要双配置对比吗？
你们可以说他不懂，但这种眼高手低，搞两个名词，乱来一气的做法，跟《小时代》受众在性质上也差不离，人家郭敬明的粉丝也不懂啦