| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2595 人关注过本帖
标题:一起来求素数
只看楼主 加入收藏
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:5 
敲错了,是VS2010
直接在打开方式里选就行


[fly]存在即是合理[/fly]
2012-12-03 23:27
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:25 
嗯,速度上是没法超越了,筛法仍然是我所知道的最快的素数算法。

这里介绍另一种素数判定方法,原理是利用费马小定理加二次探测定理来判定素数的一种概率算法。

事实上我知道这个算法要比筛法还早一些,只是一直没有使用过,借着这个机会试了一下。

关于速度,要看你怎么定义了,如果要找出一个范围内的所有素数,它的效率是不如素数筛的;但如果只判定某一个数是否是素数,它的优势非常明显,时间复杂度可以任为是O(1)。(我的代码中实际是O(log(n)),出于简化的目的,isprime不判断4以下数)。

而空间复杂度上筛法无法与这种算法相比。这也是筛法的软肋,筛法本就是一种以空间换时间的算法。

这段代码计算1千万以内的素数需要大约16秒,可以估算,计算20亿以内大约需要近1个小时。

呵呵,算是开拓一下大家的思路吧。
程序代码:
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int isprime(int n)
{
    int ps[32], a, p, x, r, t, i, j;
    for(t = -1, p = n - 1; p; p >>= 1) ps[++t] = p & 1;
    for(i = 0; i < 16; i++)
    {
        a = (rand() % (n - 2)) + 2;
        for(r = 1, j = t; j >= 0; j--)
        {
            x = r;
            r = ((long long)x * x) % n;
            if(r == 1 && x != 1 && x != n - 1) return 0;
            if(ps[j]) r = (long long)r * a % n;
        }
        if(r != 1) return 0;
    }
    return 1;
}

int main()
{
    int i, c, t0;
    srand(time(NULL));
    t0 = clock();
    for(c = 2, i = 5; i <= 10000000; i += 2)
        c += isprime(i);
    printf("count = %d\nuse time %.3f s\n", c, (double)(clock() - t0) / 1000);
    return 0;
}

重剑无锋,大巧不工
2012-12-04 10:08
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
刚刚上课时想到一种,比如关键数210=2*3*5*7,那么210到下一个关键数210*11=2320间的素数可以表示为:210N+1,210N+11,(210N+素数)形式,然后用小于 根号2320的素数判断,不知道行不行,请大神评价



[fly]存在即是合理[/fly]
2012-12-04 10:08
lz1091914999
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:四川
等 级:贵宾
威 望:37
帖 子:2011
专家分:5959
注 册:2010-11-1
收藏
得分:0 
回复 32楼 beyondyf
Rabin-Miller是根据费马小定理改进的吗?如果是概率的话,会不会有判断错误的情况出现呢?

My life is brilliant
2012-12-04 11:24
lxsjzbd
Rank: 4
来 自:河北省
等 级:业余侠客
帖 子:97
专家分:258
注 册:2012-3-31
收藏
得分:0 
楼主应该给个更厉害的程序,不然总感觉你在耍猴,
2012-12-04 12:01
beyondyf
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
等 级:贵宾
威 望:103
帖 子:3282
专家分:12654
注 册:2008-1-21
收藏
得分:0 
回复 34楼 lz1091914999
是。其实我的代码实现的就是Rabin-Miller算法。

Rabin-Miller算法本质是应用费马小定理求素数的Monte-carlo算法。

理论上误判的可能性是存在的。但通过重复测试可以将这个概率降到很低。我的代码中采用固定重复16次测试,这样可以保证误判的概率低于1/(x^32)。

事实上到现在我还没有检测到误判的数据,效果还不错。

但是出错的概率低并不意味着一定不出错,我也是因为这样的纠结,虽然十几年前就知道这个算法,但今天是第一次实现它。

平时也就玩的时候能遇到素数计算,也不需要这么大量的素数,两行代码实现个素数筛即可。如果不是有容这个题目,也许它永远尘封在我的记忆里也说不定呵呵。

重剑无锋,大巧不工
2012-12-04 12:13
雨醉
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2012-12-3
收藏
得分:0 
回复 9楼 wp231957
表示看不懂。。。。得学习学习
2012-12-04 12:33
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:0 
无视我在33楼的话,刚刚实现了,素数遗漏很多,表示无奈


[fly]存在即是合理[/fly]
2012-12-04 12:58
小小战士
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:1
帖 子:569
专家分:1313
注 册:2012-11-3
收藏
得分:0 
学习了

小小战士,战士中的战斗机!
2012-12-04 14:26
有容就大
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:东土大唐
等 级:版主
威 望:74
帖 子:9048
专家分:14309
注 册:2011-11-11
收藏
得分:0 
回复 31楼 azzbcc
可惜我Vs 换成VC2010了

梅尚程荀
马谭杨奚







                                                       
2012-12-04 14:30
快速回复:一起来求素数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.043276 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved