YXTS122
YXTS122
采纳率100%
2015-11-02 09:50

i<=sqrt(n);这种情况为什么也可以判断是不是素数?

已采纳

i <n;这种情况就是用 n 分别除以2,3,……,一直到小于n,如果都除不尽的话,就说n是素数。但实际上不用那么麻烦的,比如i<=n/2;这种情况,只需要判断到它的一半就可以了,因为一个数去除以比它的一半还要大的数一定除不尽的,所以不用再判断了。可是i<=sqrt(n);这种情况我就奇怪了,老想不通这种情况为什么也可以判断?图片图片图片图片图片图片图片

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • wwwsssaaaddd 诸相非相 6年前

    根据素数的定义反推:因为如果一个数不是素数那么它一定是两个数的乘积。 n = sqrt(n) * sqrt(n),假设n是i*j,那么i和j一定有一个是<= sqrt(n) ,另一个>=sqrt(n),因次只看较小那个除数存不存在就可以判断n是否素数。

    点赞 6 评论 复制链接分享

相关推荐