文件名称:2秒内 计算10亿内素数筛法
文件大小:187KB
文件格式:EXE
更新时间:2013-09-07 07:06:11
素数 筛法 高效
最快的素数筛法, 2秒初始化后在奔腾4上能算出2^31 以内素数个数,之后10ms内算出任意 0-2^31之间素数个数,可快速的计算第k个素数, 枚举区间[n, m](m - n < 10^5)以内素数等 还可以计算第k个数,分因素分解 Prime[78499] = 1000003 b ---------------------start benchmark------------------------ PI(2147483647) = 105097565, time use 232.64 ms k e8 -------------------start find kth prime--------------------- Prime[100000000] = 2038074743, time use 2.94 ms 10^7+100 e5-100 PI[10000100, 10100000] = 6239, time use 0.53 ms o 2^31+1 -------------------start factor prime---------------------- 2147483649 : 3 * 715827883 e9 PI(1000000000) = 50847534, time use 3.25 ms e10 e9 PI[10000000000, 11000000000] = 43336106, time use 1322.91 ms s e10 10 -------------------start print prime------------------------ PI[10000000000] = 455052511 0 prime number in range[10000000000, 10000000010] : s e10 100 -------------------start print prime------------------------ PI[10000000000] = 455052511 5 prime number in range[10000000000, 10000000100] : 10000000019 10000000033 10000000061 10000000069 10000000097