算法 一个大于2的整数N是否为素数 用2~根号下N去除
一个大于2的整数N是否为素数,可以用2~根号下N的整数去除N代替用2~根号下N-1的数去除N.
为什么可以这样代替?
为什么2~根号下N去除就可以了?
2到根号下N
人气:438 ℃ 时间:2019-10-19 17:18:55
解答
如果N是合数,则必有一个小于或者等于根号N的素因子.因为任何合数都可表示为两个或者更多个素数之积.假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N.所以合数必有(至少)一个不大于根号N的素因子.不知楼主明白了吗?
推荐
- 判断n是不是素数,只需被2~根号n之间的整数除?
- 为什么判断一个数N是否素数只需判断是否能被2到根号N即可?
- 存在整数n 使根号(p+n)+根号n是整数的质数P有几个?
- 任意给定一个大于1的整数n,试设计一个算法判定n是否为质数
- 如果a是一个大于1的整数,而所有≤根号a的素数都除不尽a,则a是素数.
- Because of the flood,this farmer didn't produce very much this year?请高手翻译下,谢谢!
- 一枚硬币掷与地上,出现正面或反面的概率各为1/2;这枚硬币掷与地上两次,都是正面的概率为1/4,可以理解为1/2×1/2;同理,一枚硬币掷与地上三次,三次都是正面的概率为1/8,也可以理解为1/2×1/2×1/2.
- 内角和与外角和的总和为2340°,求这个多边形的边数
猜你喜欢