怎样判断一个数是素数

如题所述

怎样判断一个数是素数如下:

判断n是否为素数只需用2~n/2或2~n之间的数去除就可以了,常用2~n/2,因为一个数的一半的平方大于其本身是从5开始的,解方程:n/2的平方>n 。

即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2,3也是符合下面程序的。

素数(又称质数):就是除了1和它本身,没有其他因子的整数。注:1既不是素数,也不是合数。

例如17是素数,因为它不能被2~16间。任意一整数整除。因此判断一个整数m是否为素数,只需用2~m-1之间的每一个整数去除,如果都不能被整除,那么m就是一个素数。

其实可以简化,m不必被2~m-1之间的每一个整数去除,只需被2~根号m之间的每个数去除就可以了。例如判别17是否为素数,只需使2~4之间的每一个整数去除。为什么可以做如此简化呢?

因为如果m能被2~m-1之间任意整数整除,如果这个数大于根号m,那这个数必定对应的还有一个比根号m小的因子(以16为例,2、8是它的因子,8大于4,2小于4)。

温馨提示:答案为网友推荐,仅供参考
相似回答