| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1502 人关注过本帖
标题:一个素数的问题~
只看楼主 加入收藏
godgoodli
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2009-9-17
结帖率:0
收藏
已结贴  问题点数:20 回复次数:27 
一个素数的问题~
i为要验证的数,用for(j=2;j<=i/2;j++)这种形式来验证素数时,能不能改为j<i/2?         理论上是可以的,用数学知识都可以验证,但c语言上却有差别,做机试时电脑会认为后者错。这是为什么?
搜索更多相关主题的帖子: 素数 
2009-09-17 00:44
专抓你的错
Rank: 2
等 级:论坛游民
帖 子:113
专家分:22
注 册:2009-5-12
收藏
得分:2 
试试i=4会发生什么

C/C++算法群19472277



第19次算法竞赛http://
2009-09-17 01:45
moondark
Rank: 3Rank: 3
等 级:论坛游侠
帖 子:45
专家分:158
注 册:2009-9-6
收藏
得分:2 
其实在理论上,只有当i>4的时候,你这判断的方式才算完全正确。。。
这里必须保证i/2大于根号i时,即i>4时才成立。
比如i=3,或者i=4,时你用j<i/2,得到的是2<3/2或2<4/2,这时电脑自然会报错。。
2009-09-17 08:09
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:2 
程序代码:
bool IsPrime(int n)
{
    if( n==2||n==3||n==5)
        return true;
    if(( (n-1)%6==0 ||(n-5)%6==0)&& n>=7)
    {
        for(int i=2;i<=sqrt(n);i++)
            if( n % i == 0 )
                return false;
        return true;
    }
    return false;
}


这才是素性判别的典范。
2009-09-17 10:45
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:2 
要是求  100--1000内的素数的话
偶会这样for(j = 2; j < i/2 + 10; j++)


我就是真命天子,顺我者生,逆我者死!
2009-09-17 10:53
专抓你的错
Rank: 2
等 级:论坛游民
帖 子:113
专家分:22
注 册:2009-5-12
收藏
得分:0 
以下是引用Devil_W在2009-9-17 10:45的发言:

bool IsPrime(int n)
{
    if( n==2||n==3||n==5)
        return true;
    if(( (n-1)%6==0 ||(n-5)%6==0)&& n>=7)
    {
        for(int i=2;i<=sqrt(n);i++)
            if( n % i == 0 )
                return false;
        return true;
    }
    return false;
}


这才是素性判别的典范。
写得混乱+低效

C/C++算法群19472277



第19次算法竞赛http://
2009-09-17 10:58
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
烦人的边界问题  真让人抓狂

我就是真命天子,顺我者生,逆我者死!
2009-09-17 10:59
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
回复 6楼 专抓你的错
我差点就当作 范例 Copy下去了

多亏你提醒。 悬崖勒马~~~~

我就是真命天子,顺我者生,逆我者死!
2009-09-17 11:01
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
回复 6楼 专抓你的错
混乱是因为你看不懂。

只要看这个数是6n+1还是6n+5

6n+2 6n+3 6n+4 6n的不是素数

而这6个的集合可以组成自然数集。

低效就不知道怎么看出来的。

麻烦你写个。

我之前在分析大数的素性判断。

一直没找到好的方法。
2009-09-17 11:03
BlueGuy
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:29
帖 子:4476
专家分:4055
注 册:2009-4-18
收藏
得分:0 
~~~

[ 本帖最后由 BlueGuy 于 2009-9-17 12:23 编辑 ]

我就是真命天子,顺我者生,逆我者死!
2009-09-17 11:07
快速回复:一个素数的问题~
数据加载中...
 
   



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

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