鱼C论坛

 找回密码
 立即注册
查看: 3874|回复: 7

判断质数的算法

[复制链接]
发表于 2014-6-11 23:28:32 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
求质数算法
int IsPrime1(int l)
{
        
        for(int j = 2; j < l; j++)
        {
                if(l%j==0)
                        return 0;
        }
        return 1;   
}
这个笨方法我明白

但是这个优化的方法 我死活明白不过来
int isPrime(int l)
{
        int i;
        for(i = 2;i*i <= l; i++)
        {
                if(l%i==0)
                {
                        return 0; //is not a prime
                }
        }
        return 1;   // is a prime
}
希望真懂的朋友 用白话解释一下这个优化的算法 我很笨 希望不要加一些 什么最小因子 等等专业的一些数学术语 能够让一个初中生听明白的话解释一下 拜托了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2014-6-12 04:13:40 | 显示全部楼层
额...比如说 36=4*9  如果36可以被4整除了,那还有需要去验证36/9是否可以整除?  不必了吧...
A=根号A * 根号A  如果一个A可以被一个小于 根号A 的数整除,那么就可以被另一个大于 根号A 的数整除,所以只有验证2到 根号I 的数
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-1 18:13:06 | 显示全部楼层

秒懂,学习了。。。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-8 09:25:07 | 显示全部楼层
神回复,其实也是一样的,就是你不用从2一直判断到I,只用判断到I^0.5就可以,因为后面的数你自己判断一下就知道完全不可能的,不用判断,这样算法节省资源。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-23 12:30:16 | 显示全部楼层
顶一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-25 11:50:14 | 显示全部楼层
顶一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-25 17:56:54 | 显示全部楼层
算法真是太难了。。。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2014-7-28 03:11:43 | 显示全部楼层
顶起~~~~~~~~~~~~
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 03:44

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

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