求10的10次方以内的素数，怎么能在几小时内算出来结果？

koolcoy

这个问题就是筛法最高效， 没多大的优化余地， 复杂度降不下去。 所谓优化也就是榨CPU，内存， 缓存， 榨编译器。

素数的分布目前还没发现啥规律， 任何找规律的优化方法都是徒劳。

x2

原帖由 blackuhlan 于 2009-4-24 08:39 发表
我一直想弄个大数是否质数的算法，但一直没有什么眉目，不知道兄弟们有什么好的思路。大数是指很大很大的数.

建议先弄懂：费马小定理、欧拉函数、欧拉定理、费马测试、米勒-拉宾测试之类的基础知识, 就是76楼提到的数论知识。

[ 本帖最后由 x2 于 2009-4-24 10:07 编辑 ]

x2

原帖由 皇家救星 于 2009-4-23 17:28 发表
这个不是一个算法，只是一个对概率算法的质疑。 -

--------------------------------

a除b的余数有两种，一种是0，另一种是非0

a除b后余数是0，则说明它不是素数，否则说明它有可能是素数

所以a除b ...

注意：一个整数只能被1、它本身和它的因子以及其相互乘积整除。
例如：15只能被1、15、3和5整除，2、4、6、7、8、9、10、11、12、14以及大于15的整数均不整除15.
一个整数可以表示成若干个素数的乘积：N = P1^a1 * P2^a2 * ... Pk^ak, N可被(a1+1)*(a2+1)*...(ak+1)个数整除，记为Pak，有没办法证明Pak=N/2, 即对于一个合数N, 有一半的a(1<a<N)可以整除N, 使得"a除b后余数不为0，则其是素数的概率是1/2"这个结论成立呢？

[ 本帖最后由 x2 于 2009-4-24 19:08 编辑 ]

zliming

[quote]原帖由 [i]lbaby[/i] 于 2009-4-23 23:43 发表 [url=http://bbs3.chinaunix.net/redirect.php?goto=findpost&pid=10438312&ptid=1433650][img]http://bbs3.chinaunix.net/images/common/back.gif[/img][/url]



点击下边的链接：

http://www.esnips.com/doc/4358e49f-49f8-4170-a846-5f3adb160a31/tst



选 择

Download tst.rar

就可以下载代码了


说实话，代码我也看不懂了 [/quote]

100000000内的素数count = 50847533
我用你的算法试了一下，输出的个数比1000000000还要大
于是
[root@myhost test]# vi tst.cpp

#include"Primedat.cpp"
int tst(void)
{
    string cmd;
         Primedat *tenb;
         tenb=new Primedat(100);//改为了100
         if(tenb->initdat())
         {
          cout<<"由于生成的数据很大，一一输出将耗费大量时间\n输入\"show\"显示结>
果，其它任意字符退出:";
          cin>>cmd;
        if(cmd == "show")
      {tenb->show();}
     }
         delete tenb;
         return 0;
}


[root@myhost test]# make
g++ -o tb -O3 tenb.cpp
[root@myhost test]# ls
Makefile      Primedat.cpp~  tb        tst.cpp
Primedat.cpp  Primedat.h     tenb.cpp  tst.cpp~
[root@myhost test]# ./tb
arrnum: 1
^_^ 内存初始化完成，primedat类的对象构造成功
time: 0
由于生成的数据很大，一一输出将耗费大量时间
输入"show"显示结果，其它任意字符退出:show
7 11 13 17 19 23 29 31
33 37 39 41 43 47 51 53
57 59 61 67 69 71 73 77
79 83 87 89 91 93 97 99
end
[root@myhost test]#

看到很多非素数，你是不是检查一下那里有问题？

hw123

原帖由 zliming 于 2009-4-24 15:41 发表


100000000内的素数count = 50847533
我用你的算法试了一下，输出的个数比1000000000还要大
于是
[root@myhost test]# vi tst.cpp

#include"Primedat.cpp"
int tst(void)
{
    string cmd;
      ...

汗，我昨天看见这个哥们的代码了，4秒，是很快，没仔细看答案

刚刚看到一个93了，晕菜

hw123

原帖由 koolcoy 于 2009-4-22 10:46 发表
修改了一下代码
1. 在改成了windows下vc 2005可以编译运行的
2. 参照zliming， 位图使用int*代替char*

说明一下， 位图的存取必须用宏或者inline（编译器优化成inline的也可以）， 否则函数调用的开销非常 ...

哥哥，解释一下这两个宏啥意思啊？？

#define CLEAR(map, bit) (map)[(bit) / 32] &= ~(1 << (bit % 32))
#define GET(map, bit) ((map)[(bit) / 32] & (1 << (bit % 32)))

glasslion

这题最耗时的其实是输出
不加优化的筛法初中里拿PASCAL编过求10^9以内的，用了 20分钟
不过当年的内存跑不了10^10的就没试过

皇家救星

原帖由 koolcoy 于 2009-4-24 08:51 发表
这个问题就是筛法最高效， 没多大的优化余地， 复杂度降不下去。 所谓优化也就是榨CPU，内存， 缓存， 榨编译器。

素数的分布目前还没发现啥规律， 任何找规律的优化方法都是徒劳。

我原来也以为筛法够快了

但是看一下那个huagcalc才知道错的离谱

怎么榨CPU也不可能 0~2^32-1 之间的用了才 0.000005s

这应该是靠算法上的时间复杂度不同而不是代码效率

lbaby

原帖由 zliming 于 2009-4-24 15:41 发表


100000000内的素数count = 50847533
我用你的算法试了一下，输出的个数比1000000000还要大
于是
[root@myhost test]# vi tst.cpp

#include"Primedat.cpp"
int tst(void)
{
    string cmd;
      ...

终于有兄弟实际的跑代码了，那代码确实有问题的，
是个有BUG版本，最终版是找不到了，正在使用C重写中。

win_hate

原帖由 皇家救星 于 2009-4-24 21:52 发表


我原来也以为筛法够快了

但是看一下那个huagcalc才知道错的离谱

怎么榨CPU也不可能 0~2^32-1 之间的用了才 0.000005s

这应该是靠算法上的时间复杂度不同而不是代码效率

确实厉害。不过我想确认一下，那些素数是被遍历确认的吗？换而言之，是“生成”的还是只给了个总数？