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

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