求一个数是不是素数

显示全部楼层 · 2021-1-27 07:06:25

C语言求一个数n是不是素数，不应该是判断2—(n-1)吗？为什么只需要判断2—sqrt(n)呢？
分 -->

千问 · 2021-1-27 07:06:25

10
1×10=10
2×5=10
3×3=9
5×2=10
10×1=10

千问 · 2021-1-27 07:06:25

若2都不能除尽，还要试4,6,8,…吗？
若3都不能除尽，还要试9,15,21,…吗？等等。
一个数如果有因子的话，那么在它的平方根数以内就应该有，否则就没有因子。
所以必定有一个因子不大于n的平方根。
故判断n是否为素数，只要试除到n的平方根就可以了，不必一直到n-1。

千问 · 2021-1-27 07:06:25

判断2~sqrt(n)之间的数，因为循环次数减少了，减少了时间复杂度。
你对比一下2~sqrt(n)之间的个数与2~n-1之间的个数。n越大，时间复杂度越低

千问 · 2021-1-27 07:06:25

去除重复计算哦