✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。
🍎个人主页：小嗷犬的博客
🍊个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。
🥭本文内容：C/C++中的素数判定
更多内容请见👇
@TOC
1.什么是素数
素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是素数也不是合数）。在许多的程序设计题目中，都会涉及到素数的判断，那我们该如何有效判断素数呢？
2.素数的两种判断方法
2.1 暴力法
2.1.1 从 2 到 √n
根据素数的定义，我们可以使用 逐个试除的方式来判断素数，如果能为要判断的数找到一个除了1和自身以外的因数，那么它就是合数；反之，就是素数。而这样的因数的范围必然在
2 ~ √n之间，所以我们便可以得到以下代码。
int isPrime(int n)
{
if(n <= 1)
{
return 0;
}
for (int i = 2; i * i <= n; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}该函数就可以判断输入的数是否为素数。这个范围还可以更进一步地缩小。
2.1.2 6n-1与6n+1
数学上有一个定理，除了2和3外，只有形如6n-1和6n+1的自然数可能是素数，这里的n是大于等于1的整数。如何理解这个定理呢？
所有自然数都可以写成6n,6n+1,6n+2,6n+3,6n+4,6n+5这6种。
那么我们就可以得到下表。
| 自然数 | 是否可能是素数 |
|---|---|
6n |
不可能，为2的倍数 |
6n+1 |
可能 |
6n+2 |
不可能，为2的倍数 |
6n+3 |
不可能，为3的倍数 |
6n+4 |
不可能，为2的倍数 |
6n+5 |
可能 |
其中6n+5可以写作6n-1，所以除了2和3的素数必然形如6n-1或6n+1。
于是我们可以写出如下代码。
int isPrime(int n)
{
if(n <= 1) return 0;
else if(n == 2 || n == 3) return 1;
else if(n % 6 != 1 && n % 6 != 5) return 0;
for (int i = 5; i * i <= n; i++)
{
if (n % i == 0)
{
return 0;
}
}
return 1;
}优化后的算法具有更高的效率。
2.2 筛法
暴力算法虽然可以判断某个数是否为素数，但是当它面对大量需要判断的数据时，它的效率会显得十分低下，我们也有更好地方法来求一定范围里的素数，它就是我们的 筛法。筛法，顾名思义，就是将合数从数据中筛除，剩下的自然就都是素数了。
筛法也分为两种，让我们来逐一介绍。
2.2.1 埃氏筛
埃拉托斯特尼 筛法，简称 埃氏筛，是一种由希腊数学家 埃拉托斯特尼所提出的一种简单检定素数的算法。要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。
下面的程序就是通过埃氏筛判断
2 ~ MAXSIZE-1是否为素数。
#define MAXSIZE 10000
int isPrime[MAXSIZE] = {0};
int prime[MAXSIZE];
int cnt = 0;
void sieveOfEratosthenes()
{
for (int i = 2; i < MAXSIZE; i++)
{
isPrime[i] = 1;
}
for (int i = 2; i * i < MAXSIZE; i++)
{
if (isPrime[i])
{
prime[++cnt] = i;
for (int j = i * 2; j < MAXSIZE; j += i)
{
isPrime[j] = 0;
}
}
}
}埃氏筛的时间复杂度是O(n*loglogn)，效率相较于原来的暴力算法已经有了很大的提高，但它仍然有具有一定的不足。对于多个素数的公倍数，可能会被多次筛去。
为了解决这个问题，数学家欧拉优化了算法，于是就有了新的筛法。
2.2.2 欧拉筛
欧拉筛法，简称 欧拉筛或是欧式筛，又因为其O(n)的时间复杂度而被称为 线性筛。欧拉筛将合数分解为（
最小质因数 * 一个合数）的形式，通过最小质因数来判断当前合数是否已经被标记过，与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。下面的程序就是通过欧拉筛判断
2 ~ MAXSIZE-1是否为素数。
#define MAXSIZE 10000
int isPrime[MAXSIZE];
int prime[MAXSIZE];
int cnt = 0;
void sieveOfEuler()
{
for (int i = 2; i < MAXSIZE; i++)
{
prime[i] = 1;
isPrime[i] = 1;
}
for (int i = 2; i * i < MAXSIZE; i++)
{
if (isPrime[i])
{
prime[++cnt] = i;
}
for (int j = 1; i * prime[j] < MAXSIZE; j++)
{
isPrime[i * prime[j]] = 0;
//若i为prime[j]的倍数，终止循环，避免重复筛除
if (i % prime[j] == 0)
break;
}
}
}在求一定范围中的所有素数时，欧拉筛具有无可比拟的优势，在程序设计中也经常被采用。
