论坛 › 编程擂台 › 10秒内计算出1亿素数表, 不输出

无心人 发表于 2009-1-1 22:47:46

基本上到了筛法的后期
都是在优化算法细节上做文章

算法本身应该改动不大了

tprime 发表于 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

无心人 发表于 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 & 7) & 1;
    }

    public static void main(String args[])
    {
      int i = 100;
      try
      {
            i = Integer.parseInt(args);
      }
      catch(Exception exception) { }
      int j = (i + 1) / 2;
      isprime = new byte;
      int k = 0;
      for(int l = 0; l <= j / 8 + 1; l++)
            isprime = -1;

      isprime &= 0xfe;
      isprime |= 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 &= ~(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 &= ~(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
输入新时间:

sir_chen 发表于 2009-12-8 21:15:14

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

sir_chen 发表于 2009-12-8 21:21:06

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

qianyb 发表于 2010-2-27 15:10:10

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

gxqcn 发表于 2010-2-27 15:39:35

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

查看完整版本: 10秒内计算出1亿素数表, 不输出