判断素数质数的四种方法

普通解法
根据素数的定义除了1和它本身没有其他的因数，就是素数，所以把数用从2~数本身-1的数字除于看看有没有被整除，如果没有被整除那么这个数就是质数。这个办法只适用于用于被判断数较小的情况。数字太大会非常慢。
时间复杂度O(n)
样例代码（C ）

bool judgement_prime(int n)
{
	for (int i = 2; i < n - 1; i  )
		if (n % i == 0)
			return false;
	return true;
}

根号解法（笔者自己取得名字，滑稽）
根号解法是普通解法的优化版，普通解法是判断数字m是不是素数时得从2除到m-1但是本质上不需要除到n-1.n 不必被 2 ~ n-1 之间的每一个整数去除，只需被 2 ∽ ( n ) 2 \backsim\sqrt(n) 2∽( n) 之间的每一个整数去除就可以了。如果 n 不能被 2 ∽ ( n ) 2 \backsim\sqrt(n) 2∽( n) 间任一整数整除，n 必定是素数。原因：因为如果 n 能被 2 ~ n-1 之间任一整数整除，其二个因子必定有一个小于或等于根号n ，另一个大于或等于根号n 。
时间复杂度O(根号n)
样例代码（C ）

bool judgement_prime_sqrt(int n)
{
	for (int i = 2; i <= sqrt(n); i  )
		if (n % i == 0)
			return false;
	return true;
}

普通筛选法–埃拉托斯特尼筛法
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为n 1的数组保存信息（0表示素数，1表示非素数，这个不是固定的也可以是1表示素数，0表示和数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于n；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。
说明：整数1特殊处理即可。
时间复杂度O(nloglogn)
样例代码（C ）

bool judgement_prime_screen(int n)
{
	//根据需要开数组大小别开太小了
	//标记下标数字是不是素数，false是素数true不是素数
	bool* flag = new bool[128];
	//记录素数
	int* prime = new int[128];
	//默认所有数字都是素数
	fill(flag, flag   128, false);
	flag[0] = flag[1] = true; //0，1不是素数
	int cut = 0;	//发现的素数个数
	//筛选出0到n的所有素数并记录
	for (int i = 2; i <= n;   i)
	{
		//记录素数
		if (!flag[i])
			prime[cut  ] = i;
		//标记素数的倍数为不是素数
		for (int j = i   i; j <= n; j  = i)
			flag[j] = true;
	}
	//prime数组里存着所有找到素数
	//flag标记着下标是不是素数
	//cut是发现的素数个数
	//可以看情况进行利用
	//例如判断n是不是素数直接
	return !flag[n];	
	//因为false标记的素数所以返回时可取反返回
	//这样是素数就true不是则false
}

线性筛法–欧拉筛法
不难看出，埃氏筛法仍有优化空间，它会将一个合数重复多次标记。如果我们能有办法保证每个数都只会被筛一次那么时间复杂度能大大降低了。欧拉筛法就做到了一点，筛一个数的时候保证只在最小的素数因子对的时候筛出。例如12，可以把12分解为(2,6)(3,4),欧拉筛保证会在发现(2,6)因子对的时候筛出他而并不是在(3,4)的时候。
样例代码（C ）

bool judgement_prime_screen_pro(int n)
{
	//标记下标数字是不是素数，false是素数true不是素数
	bool* flag = new bool[128];
	//记录素数
	int* prime = new int[128];
	//默认所有数字都是素数
	fill(flag, flag   128, false);
	flag[0] = flag[1] = true; //0，1不是素数
	int cnt = 0;	//发现的素数个数
	//筛选出2到n的所有素数并记录
	for (int i = 2; i <= n; i  )
	{
		if (!flag[i])//不是目前找到的素数的倍数 
			prime[cnt  ] = i;//找到素数
		for (int j = 0; j < cnt && i * prime[j] <= n; j  )
		{
			//标记素数的倍数为不是素数
			flag[i * prime[j]] = true;
			//保证每次值会在最小的质数因子对的时候进行筛选
			if (i % prime[j] == 0)
				break;
		}
	}
	//prime数组里存着所有找到素数
	//flag标记着下标是不是素数
	//cut是发现的素数个数
	//可以看情况进行利用
	//例如判断n是不是素数直接
	return !flag[n];
	//因为false标记的素数所以返回时可取反返回
	//这样是素数就true不是则false
}

if(i % prime[j] == 0) break;这一步是关键，也是比较费解的。任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们要保证能找到的是有最小质因子的数对。 当i是prime[j]的整数倍时，i*prime[j 1]肯定被筛过，跳出循环。
因为如果$$i\%prime[j]=0$$那么就会存在一个x成立
$$prime[j]\times x=i$$当然也肯定有个y能成立
$$prime[j1]\times y=i$$
因为prime[j] 一定小于prime[j 1]所以prime[j 1]已经不可能是i的最小质因子了，往后就没必要计算了。

练习题
洛谷质数口袋
洛谷质数口袋解析

这篇好文章是转载于：学新通技术网