A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 黄少海 中级黑马   /  2013-7-2 09:49  /  1379 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 黄少海 于 2013-7-2 11:31 编辑

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

  1. <P> private static boolean isPrime(int n) {//判定一个数是否是素数</P>
  2. <P>  for(int i=2; i<=n/2; i++){
  3.    if(n%i==0){
  4.     return false;
  5.    }
  6.   }
  7.   return true;
  8. }</P>
复制代码
其中for循环中 i<n 跟 i<=n/2有什么不同? 判定一个素数只要判定它不被1跟它本身以外的数整除。这是用i<n来判定条件的范围。为什么还要n要除以2。

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

5 个回复

倒序浏览
2是除了1最小的因子。小于等于n/2就是判断n/2是否也能被n整除,如果可以的话说明这个数还有2这个因子,就不是素数,这样做减少了循环的次数提高效率

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

回复 使用道具 举报
这是纯粹的数学问题,于编程无关。在求素数时,所使用的最小除数是2即for循环中的i=2,如果i>n/2除出来的结果势必比2小,若为整数只能是1。
故循环条件设置为i>n/2,以减少循环次数,节约系统资源。

评分

参与人数 1技术分 +1 收起 理由
袁梦希 + 1 很给力!

查看全部评分

回复 使用道具 举报

楼主你好  如果帖子的问题已经解决,请把帖子的类型改为“已解决”。
回复 使用道具 举报
继续努力  {:soso__14347937040236606360_1:}
回复 使用道具 举报 1 0
例如 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之间有因数。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马