1.什么是素数

素数又称质数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定1既不是素数也不是合数）。

在许多的程序设计题目中，都会涉及到素数的判断，那我们该如何有效判断素数呢？

2.素数的两种判断方法

（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;
}

该函数就可以判断输入的数是否为素数。

这个范围还可以更进一步地缩小。

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）筛法

暴力算法虽然可以判断某个数是否为素数，但是当它面对大量需要判断的数据时，它的效率会显得十分低下，我们也有更好地方法来求一定范围里的素数，它就是我们的筛法。

筛法，顾名思义，就是将合数从数据中筛除，剩下的自然就都是素数了。

筛法也分为两种，让我们来逐一介绍。

埃氏筛

埃拉托斯特尼筛法，简称埃氏筛，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

埃氏筛

下面的程序就是通过埃氏筛判断 0 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };

void sieveOfEratosthenes()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		isPrime[i] = 1;
	}
	for (int i = 2; i * i < MAXSIZE; i++)
	{
		if (isPrime[i])
		{
			for (int j = i * 2; j < MAXSIZE; j += i)
			{
				isPrime[j] = 0;
			}
		}
	}
}

埃氏筛的时间复杂度是O(n*loglogn)，效率相较于原来的暴力算法已经有了很大的提高，但它仍然有具有一定的不足。

对于多个素数的公倍数，可能会被多次筛去。

为了解决这个问题，数学家欧拉优化了算法，于是就有了新的筛法。

欧拉筛

欧拉筛法，简称欧拉筛或是欧式筛，又因为其O(n)的时间复杂度而被称为线性筛。

欧拉筛将合数分解为（最小质因数 * 一个合数）的形式，通过最小质因数来判断当前合数是否已经被标记过，与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。

下面的程序就是通过欧拉筛判断 0 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = { 0 };
int prime[MAXSIZE];
int cnt = 0;

void sieveOfEuler()
{
	for (int i = 2; i < MAXSIZE; i++)
	{
		prime[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;
		}
	}
}