编写一个函数判断是否为素数(判断是否为素数)

姚枫罡
导读 大家好,乐天来为大家解答以下的问题,关于编写一个函数判断是否为素数,判断是否为素数这个很多人还不知道,现在让我们一起来看看吧!1、判

大家好,乐天来为大家解答以下的问题,关于编写一个函数判断是否为素数,判断是否为素数这个很多人还不知道,现在让我们一起来看看吧!

1、判断是否是质数最直观和简单的方法就是从2开始直接除,能除尽(余数为0)就不是质数。

2、则C语言实现为:int isprime(int m){int i;for(i=2;i

3、可以改进一下,根据如果一个数是合数,那么它的最小质因数肯定小于等于它的平方根。

4、用反证法可以证明一下。

5、假设x是n的最小质因数,则存在n/x=p。

6、p>x,x*p=n。

7、如果x不小于等于它的平方根,则x*x>n,而p>x,故x*p>n,假设不成立。

8、合数是与质数相对应的自然数。

9、一个大于1的自然数如果它不是合数,则它是质数。

10、也就是说如果一个数能被它的最小质因数整除的话,那它肯定是合数,即不是质数。

11、所以判断一个数是否是质数,只需判断它是否能被小于它开跟号后的所有数整除,因此,这样做的运算少了很多,降低了时间复杂度。

本文分享完毕,希望对大家有所帮助。

标签:

免责声明:本文由用户上传,如有侵权请联系删除!