数学研发论坛

 找回密码
 欢迎注册
楼主: 无心人

[讨论] 10秒内计算出1亿素数表, 不输出

[复制链接]
 楼主| 发表于 2009-1-1 22:47:46 | 显示全部楼层
基本上到了筛法的后期
都是在优化算法细节上做文章

算法本身应该改动不大了
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-2-2 09:46:09 | 显示全部楼层
附件中有多 个素数和孪生素数程序,后面的数字表示
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

Prime.zip

335.48 KB, 下载次数: 10, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

售价: 1 枚金币  [记录]

最新版素数和孪生素数计算程序

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-2-2 14:03:45 | 显示全部楼层
这个似乎和机器的二级缓存关系比较大

但具体的关系不是太简单的
似乎略微大于所有的缓存的和
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-7-31 18:49:46 | 显示全部楼层
本帖最后由 〇〇 于 2009-7-31 18:58 编辑

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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2009-8-2 10:47:18 | 显示全部楼层
希望能给出一些具体的测试信息
比如时间
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-11-7 19:11:20 | 显示全部楼层
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
输入新时间:

SIEVE5.cpp

4.73 KB, 下载次数: 2, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

cr

2 Bytes, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

test.bat

63 Bytes, 下载次数: 1, 下载积分: 金币 -1 枚, 经验 1 点, 下载 1 次

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-8 21:15:14 | 显示全部楼层
能不能把实现的过程说的详细一点
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2009-12-8 21:21:06 | 显示全部楼层
能不能把原理说清楚,代码都是次要的
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-27 15:10:10 | 显示全部楼层
郭老大的PrimeNumber素数生成的内存要求太高了,生成42亿时700M空闲内存还提示不够
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2010-2-27 15:39:35 | 显示全部楼层
主要是输出字串需要大量空间(我没有用磁盘映射技术,也未分段处理),
如果不输出,均可快速处理;
而若要输出,请选择合适的分段处理。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2020-12-5 19:55 , Processed in 0.071104 second(s), 18 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表