求证:给定一个数n,若其不能被[2]~[根号n]内的所有数整除,则n为素数.

Question

求证:给定一个数n,若其不能被[2]~[根号n]内的所有数整除,则n为素数.

Answer 1

反证法：
假设n不是素数，那么n在2-n之间必然至少有两个整数因子！设两因子为a和b，并且a<=b,则a*b=n，a=n/b;则可知a<=(根号n的上限);(这里如果a>(根号n的上限)的话，a*b>n;)所以，可以得出a可以整除n，那么与条件“其不能被[2]~[根号n]内的所有数整除”矛盾，那么假设不成立。故可以得出“给定一个数n,若其不能被[2]~[根号n]内的所有数整除,则n为素数.”的结论。