回复内容：
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 ; i Nmax ; i += 2 )
isPrime [ i ]= true ;
isPrime [ 2 ]= true ;
for ( int i = 3 ; i Math . sqrt ( Nmax ); i += 2 ){
if ( isPrime [ i ]== true ){
for ( int j = i * i ; j Nmax ; j += 2 * i )
isPrime [ j ]= false ;
}
}
int primeNum = 0 ;
for ( int i = 1 ; i Nmax ; 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秒解出来。 Mathematica可以在0.012001秒解出来。 http:// quartergeek测试数据/sieve-p rime-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 ; i q ; ++ i ){
if ( ! b [ i ] ){
for ( j = i 1 ; j N ; j += i ){
b [ j ] = true ;
}
}
}
for ( i = 2 ; i N ; ++ 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 ; i N ; ++ i ){
if ( ! b [ i ] ){
c [ cnt ++ ] = i ;
}
for ( j = 0 ; j cnt ; ++ 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 ; i num ; ++ i ){
Era_select ();
}
printf ( "%lf seconds \n " , ( double )( clock () - start ) / CLOCKS_PER_SEC / num );
start = clock ();
for ( i = 0 ; i num ; ++ i ){
Euler_select ();
}
printf ( "%lf seconds \n " , ( double )( clock () - start ) / CLOCKS_PER_SEC / num );
return 0 ;
}
stackoverflow上有个关于用python求解最快算法的讨论（optimization ），如果用纯python语言的话，最快的算法是下面这个： def rwh_primes2 ( n = 10 ** 6 ):
# http://stackoverflow测试数据/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秒的程序有必要写清楚型号配置吗？ 如果不是我必须表现得礼貌，我会问你觉得这种垃圾有必要双配置对比吗？ 你们可以说他不懂，但这种眼高手低，搞两个名词，乱来一气的做法，跟《小时代》受众在性质上也差不离，人家郭敬明的粉丝也不懂啦
如果你随便玩玩，忽略这些话
如果想好好学，那么建议摆正心态，脚踏实地，不要走火入魔，误入歧途。想要成功，要牢记3点，1是切忌南辕北辙，2是不能说太多， 如果不要求准确值的话，用估算好了，x/ln(x)
以前为了算某个群号，曾经计算了八千万以内的素数，花了两秒钟。群里有个人0.2秒，觉得很牛逼，始终没明白是怎么做的。
我的做法很简单，给出八千万个bool（其实可以去掉偶数）。一开始拿出2，把2的倍数都true了。下一个false的是3，把3的倍数都true了。下一个false的是5，把5的倍数都true了。一只做到完。
查看更多关于如何编程最快速度求出两百万以内素数个数（不限语言和算法）？的详细内容...
声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did83274