试除法 假设验证自然数n是不是质数。 1.可以验证n是否能被2~n-2整除,能整除的话则是合数,否则是质数 2.一个数如果可以因数分解的话,那么两个因数一个大于等于sqrt(n)一个小于等于sqrt(n),如果在sqrt(n)的范围内找不到一个整数整除n,那么在大于sqrt(n)到n的范围内也找不到一个整数可以整除n。所以只需要求解验证2~sqrt(n)以内的数是否可以整除n。 3.因为除2以外所有的质数都是奇数,所以不需要验证偶数,只需要验证3~sqrt(n)的之间的奇数就可以。 4.继续总结,比如不能被3整除,…