判断质数的算法

500年前 · 发表于 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
}
希望真懂的朋友用白话解释一下这个优化的算法我很笨希望不要加一些什么最小因子等等专业的一些数学术语能够让一个初中生听明白的话解释一下拜托了

elvo · 发表于 2014-6-12 04:13:40

额...比如说 36=4*9 如果36可以被4整除了,那还有需要去验证36/9是否可以整除? 不必了吧...
A=根号A * 根号A 如果一个A可以被一个小于根号A 的数整除,那么就可以被另一个大于根号A 的数整除,所以只有验证2到根号I 的数

河蟹代码 · 发表于 2014-7-1 18:13:06

elvo 发表于 2014-6-12 04:13

登录/注册后可看大图

额...比如说 36=4*9 如果36可以被4整除了,那还有需要去验证36/9是否可以整除? 不必了吧...
A=根号A * 根 ...

秒懂，学习了。。。。。

骑着蜗牛旅行 · 发表于 2014-7-8 09:25:07

神回复，其实也是一样的，就是你不用从2一直判断到I，只用判断到I^0.5就可以，因为后面的数你自己判断一下就知道完全不可能的，不用判断，这样算法节省资源。

繁空.星雨 · 发表于 2014-7-23 12:30:16

顶一下

虫虫♀青丝 · 发表于 2014-7-25 11:50:14

顶一下

wangerwanger · 发表于 2014-7-25 17:56:54

算法真是太难了。。。

mumudontcry · 发表于 2014-7-28 03:11:43

顶起~~~~~~~~~~~~

账号		自动登录	找回密码
密码			立即注册