质数的判断（C）

质数的定义及性质

定义：

设N为大于1的任意整数，若N的因数只有1和N，则N称为质数。

性质：

1.非2的偶数不是质数 2.所有大于10的质数个位数必然为1，3，7，9

更多性质 详见度娘：https://baike.baidu.com/item/质数/263515?fr=aladdin 当然还有一些别的性质啦，比如什么6的附近咋样咋样的，这里因为我没用，所以就不介绍了。

分析

a: 2这个偶数是质数，如果我们想要不对所有偶数进行判断的话，则必须对2处理，处理之后我们可以使任意偶数不进入判断循环。您一路走好~

b: 利用质数的第2条性质，我们可以使大于10但个位数为5的所有数不进入循环。拜拜了您！个5

c: 在分析a中我们把所有偶数滤过了，能进循环的只能是奇数！而奇数的因数不可能有偶数，那我的为何还要循环去判断某一偶数是不是因数呢是吧？将循环初始条件为i=3,步长为2。哎打扰了呀，偶数判断再见！

d: 判断质数的因数时我们只需要判断到该数的开方就可以了。不多说，因为因数不甘孤独，都是成对出现的。我举个栗子：比如21，其因数对有（1，21）、（3，7）再如54，因数对有（1，54）、（2，27）、（3，18）、（6，9）。从来没有甘于孤独的因数，不信你再试试别的数。你再看看因数对中小的那个有没有超过判断目标的开方？没吧？所以我们判断到开方就行了。

C实现

int isPrimeNum(int x) //返回值为1：质数 0：非质数 { if (x == 2) { //处理2 return 1; } if ((x % 2 == 0) || (x > 10 && x % 10 == 5)) { return 0; //处理偶数及个5 } else { for (int i = 3; i <= pow(x, 0.5); i += 2) { //跳偶因数，上限为开方向下取整 if (x % i == 0) { return 0; break; } } } return 1; }

代码看着有点多，但效率还不错。对了，我没处理输入，假定输入一定是大于1的整数，你要是输入不符合这个规则的东西，辣我也没滴办法。你要是想提高逼格，可以加处理输入的代码。

扩展

如果我们可以将判断得到的质数存入数组，我们还可以利用已知的质数去判断下一个数是不是质数，进一步提高判断效率，这个思想可以用在输出max以下所有质数这种情况。这里我用python实现以下：

import math x = [2,3,5,7] #10以内的质数 max = 100 #目标区间[1，max] for i in range(11,max+1,2): #大于10开始，只判奇数 if i == 5: #末位为5必不是质数 continue for j in x: if j > math.ceil(i**0.5): #判到开方 x.append(i) break if not i%j: #j是i的因数，跳出 break print(x)