Question

判断一个正整数是不是素数

从小到大用每一个素数2，3，5，7，···，依次去试除所给的正整数，如果除得的商比除数小，但仍不能整除，它就是素数。
为什么商比除数小就可以判定它是素数了？

Answer 1

a÷b=c→a÷c=b。
a如果能被b整除，那么a一定也能够被商c整除。
所以在做整除时，每一个较小的除数，总有一个较大的对应的商数。
如果除到商开始比除数小的时候，还没有出现整除的情况，后面再大的除数也不用再试了。因为后面如果存在一个较大的除数能够整除，那么在这之前它所对应的较小的那个商数，也早就能整除。既然没有发现那个较小的能整除的数，自然后面较大的能整除的除数也不可能存在了。
通常我们在检查一个数是否是素数时，可以从2，3，5，7……逐个试除，除到这个数的平方根附近的整数就可以结束。在这个范围内有整除，它就不是素数，没有整除，就可以判断它是个素数。
例如127是否是素数？可以用2，3，5 ，7，11去逐个试除，11以后的数就不用考虑了，因为127的平方根在11附近。

Answer 2

是对的，大于3.不能被2整除，也不能被n/2整除，大于n/2的数肯定不能被整除，如果整除了，商小于2，肯定是1.这个n/2可以该为根号n，如果一个能被一个大于根号n的整数整除，那么商肯定小于根号n，所以也能被小于根号n整除，因此只要不能被小于根号n的整数整除，就一定不能被大于根号n的整数整除，只需要验证到根号n就可以了