10秒内计算出1亿素数表, 不输出

无心人

基本上到了筛法的后期 都是在优化算法细节上做文章 算法本身应该改动不大了

tprime

附件中有多 个素数和孪生素数程序，后面的数字表示 cache利用的大小，测试发现相同机器不同L2 cache大小计算 总时间相差很大. 接近1/4 L2 或者 L1 性能最好。 PrimeNumber33.exe TwinPrime33.exe TwinPrime66.exe PrimeNumber66.exe PrimeNumber49.exe TwinPrime49.exe PrimeNumber_33.exe TwinPrime_33.exe

无心人

这个似乎和机器的二级缓存关系比较大 但具体的关系不是太简单的 似乎略微大于所有的缓存的和

〇〇

1# 无心人 http://blog.csdn.net/l1t/archive/2006/02/23/607302.aspx import java.io.PrintStream; public class Sieve5 { public Sieve5() { } public static int getisp(int i) { return isprime[i >> 3] >> (i & 7) & 1; } public static void main(String args[]) { int i = 100; try { i = Integer.parseInt(args[0]); } catch(Exception exception) { } int j = (i + 1) / 2; isprime = new byte[j / 8 + 2]; int k = 0; for(int l = 0; l <= j / 8 + 1; l++) isprime[l] = -1; isprime[0] &= 0xfe; isprime[0] |= 2; int k1 = (int)Math.ceil(Math.sqrt(i)); boolean flag = false; int i1 = (i - 1) / 2; for(int i2 = 4; i2 <= i1; i2 += 3) isprime[i2 >> 3] &= ~(1 << (i2 & 7)); char c = '\0'; int j2 = (k1 - 1) / 2; int k2 = (i - 1) / 2; for(int j1 = 2; j1 <= j2; j1++) { c++; if(c == '\003') c = '\0'; else if(getisp(j1) == 1) { int l1 = ((j1 << 2) + 1) % 3; for(int l2 = j1 * (2 * j1 + 2); l2 <= k2; l2 = l2 + j1 + j1 + 1) if(++l1 == 3) l1 = 0; else if(getisp(l2) == 1) isprime[l2 >> 3] &= ~(1 << (l2 & 7)); } } int i3 = 2; if(i <= 2) i3 = 2; else if(i % 2 == 1 && getisp((i - 1) / 2) == 1) { i3 = i; } else { i3 = i - 1 - i % 2; do { int j3 = (i3 - 1) / 2; if(getisp(j3) == 1) break; i3 -= 2; } while(true); } System.out.println("The largest prime less than or equal to " + i + " is " + i3 + " cycle time:" + k); } static byte isprime[]; } http://topic.csdn.net/t/20040513/21/3065034.html

无心人

希望能给出一些具体的测试信息 比如时间

〇〇

85# 无心人 D:\lt\dl\sieve>cl sieve5.cpp -O2 Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80x86 Copyright (C) Microsoft Corporation 1984-2002. All rights reserved. sieve5.cpp Microsoft (R) Incremental Linker Version 7.10.3077 Copyright (C) Microsoft Corporation. All rights reserved. /out:sieve5.exe sieve5.obj D:\lt\dl\sieve>test sieve5 100000000 start ... 当前时间: 19:08:50.06 输入新时间: The largest prime less than or equal to 100000000 is 99999989, cycle time:0 当前时间: 19:08:50.65 输入新时间: done! D:\lt\dl\sieve>test sieve5 100000000 start ... 当前时间: 19:08:52.76 输入新时间: The largest prime less than or equal to 100000000 is 99999989, cycle time:0 当前时间: 19:08:53.34 输入新时间:

sir_chen

能不能把实现的过程说的详细一点

sir_chen

能不能把原理说清楚,代码都是次要的

qianyb

郭老大的PrimeNumber素数生成的内存要求太高了，生成42亿时700M空闲内存还提示不够

gxqcn

主要是输出字串需要大量空间（我没有用磁盘映射技术，也未分段处理）， 如果不输出，均可快速处理； 而若要输出，请选择合适的分段处理。