500年前 发表于 2014-6-11 23:28:32

判断质数的算法

求质数算法
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 static/image/common/back.gif
额...比如说 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

顶起~~~~~~~~~~~~
页: [1]
查看完整版本: 判断质数的算法