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

学习 时间:2026-11-20 16:38:22 阅读:8030
算法 一个大于2的整数N是否为素数 用2~根号下N去除一个大于2的整数N是否为素数,可以用2~根号下N的整数去除N代替用2~根号下N-1的数去除N.为什么可以这样代替?为什么2~根号下N去除就可以了?2到根号下N

最佳回答

正直的外套

儒雅的蛋挞

2026-11-20 16:38:22

如果N是合数,则必有一个小于或者等于根号N的素因子。因为任何合数都可表示为两个或者更多个素数之积。假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N。所以合数必有(至少)一个不大于根号N的素因子。不知楼主明白了吗?

最新回答共有2条回答

  • 英俊的嚓茶
    回复
    2026-11-20 16:38:22

    如果N是合数,则必有一个小于或者等于根号N的素因子。因为任何合数都可表示为两个或者更多个素数之积。假如N是合数且其素因子都大于根号N,那么将产生矛盾:根号N*根号N>N。所以合数必有(至少)一个不大于根号N的素因子。不知楼主明白了吗?

上一篇 填三字词语 

下一篇 为什么冥王星会被踢出9大行星