Question

判断质数（素数）的要求

在书上看到:判断a是否质数，只要看它能否被2~√a（ 范围 : 2 到 根号a ) 里面的数整除就可以了。我想知道√a的范围是怎么出来的。

Answer 1

假设a=s×t， s,t≠1，不妨设s≤t
则a=s×t ≥ s×s = s²
则 s ≤ √a，
即如果一个数a不是质数，那么他分解得到的两个约数，必然有一个不大于√a
所以，只要确定2~√a之间没有a的约数，即不能被2~√a之间的数整除，那么a就是质数

Answer 2

因为a如果是合数，一定可以分解为两数之积。设两数分别为b和c，且b<=c，则有a=b*c，即a能被b和c整除
而a=(√a)^2，所以有(√a)^2=b*c
因为b<=c，所以可知b<=√a
也就是说如果a是合数，则必然能被某一个整数b整除，且b<=√a，得证。
注：b<=√a是因为：反证法，不妨假设b>√a，则必有c>√a，因此必有b*c>a，矛盾，假设不成立，因此有b<=√a。

全是一点点打得，应该已经够详细了，望采纳，谢谢

Answer 3

假设a=bc，且b＜√a，那么必然有c＞√a，才能得到a=bc
也就是说如果自然数a能被√a以内的数整除，那么在√a~a之间必然还有一个因数，
故只需要判断√a以内即可，他们是一一对应的

例如判断91是不是质数，先计算√91在9~10的范围内，故只需在2~9中寻找，并且只需要寻找个位是1、3、7、9的数