作业帮 > 数学 > 作业

算法 一个大于2的整数N是否为素数 用2~根号下N去除

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/05/13 09:17:47
算法 一个大于2的整数N是否为素数 用2~根号下N去除
一个大于2的整数N是否为素数,可以用2~根号下N的整数去除N代替用2~根号下N-1的数去除N.
为什么可以这样代替?
为什么2~根号下N去除就可以了?
2到根号下N
如果N是合数,则必有一个小于或者等于根号N的素因子.因为任何合数都可表示为两个或者更多个素数之积.假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N.所以合数必有(至少)一个不大于根号N的素因子.不知楼主明白了吗?