为什么只需使n被2~√n之间的整数除即可判定n是否为素数?想不明白这个原理,

分类: 作业答案 • 2022-01-02 13:29:18

问题描述：

为什么只需使n被2~√n之间的整数除即可判定n是否为素数?
想不明白这个原理,

答

如果n不是素数,那么至少可以表示为不为1的两个整数的乘积
n=xy
而x,y两个数要么一样,要么有大小
若x=y,那么x=√n,所以√n整除n
若x与y不等,假设xx*x
x1）整除n
综上,使n被2~√n之间的整数除即可判定n是否为素数