黑马程序员技术交流社区

标题: 判断素数的这两个方法有什么区别？ [打印本页]
作者: 黄少海    时间: 2013-7-2 09:49
标题: 判断素数的这两个方法有什么区别？
本帖最后由 黄少海 于 2013-7-2 11:31 编辑

  2. <P> private static boolean isPrime(int n) {//判定一个数是否是素数</P>
  3. <P>  for(int i=2; i<n; i++){
  4.    if(n%i==0){
  5.     return false;
  6.    }
  7.   }
  8.   return true;
  9. }
  10. </P>
复制代码

  2. <P> private static boolean isPrime(int n) {//判定一个数是否是素数</P>
  3. <P>  for(int i=2; i<=n/2; i++){
  4.    if(n%i==0){
  5.     return false;
  6.    }
  7.   }
  8.   return true;
  9. }</P>
复制代码
其中for循环中 i<n 跟 i<=n/2有什么不同？ 判定一个素数只要判定它不被1跟它本身以外的数整除。这是用i<n来判定条件的范围。为什么还要n要除以2。
作者: 王靖远    时间: 2013-7-2 10:13
2是除了1最小的因子。小于等于n/2就是判断n/2是否也能被n整除，如果可以的话说明这个数还有2这个因子，就不是素数，这样做减少了循环的次数提高效率
作者: 宋智超    时间: 2013-7-2 10:14
这是纯粹的数学问题，于编程无关。在求素数时，所使用的最小除数是2即for循环中的i=2，如果i>n/2除出来的结果势必比2小，若为整数只能是1。
故循环条件设置为i>n/2,以减少循环次数，节约系统资源。
作者: 杜光    时间: 2013-7-2 10:37

楼主你好  如果帖子的问题已经解决，请把帖子的类型改为“已解决”。
作者: 袁梦希    时间: 2013-7-2 12:36
继续努力  {:soso__14347937040236606360_1:}
作者: 王楚鑫    时间: 2013-7-2 13:07
例如 17是素数，因为它不能被2~16间任意一整数整除。因此判断一个整数n是否为素数，只需用2~n-1之间的每一个整数去除，如果都不能被整除，那么n就是一个素数。其实可以简化，n不必被2~n-1之间的每一个整数去除，只需被2~根号n之间的每个数去除就可以了。例如判别17是否为素数，只需使2~4之间的每一个整数去除。为什么可以做如此简化呢？因为如果n能被2~n-1之间任意整数整除，如果这个数大于根号n，那这个数必定对应的还有一个比根号n小的因子（以16为例，2、8是它的因子，8大于4，2小于4）。判断n是否为素数还可用2~n/2的数去除，因为一个数的一半的平方大于其本身是从5开始的，解方程：n/2的平方>n 。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2