判断是否为质数的超级优化 C++语言（超详细）

首先我们要知道质数的概念：

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

知道了质数的概念，我们就可以大胆的说：“老师，我可以跑暴力”————》开个for循环从2怼到n-1，如果n被其整除那么就不是质数，反正是质数。

还是老话：“暴力解决不了所以问题，就比如时间上可能会很慢（因为你是在完全借助质数的定义跑循环）。”

所以要 优化！优化！ 优化！

#include
#include
using namespace std;
bool Prime_Numbers(int x)
{
	int tmp = sqrt(x);
	for(int i = 2;i<=tmp;i++)
	{
		if(x%i==0)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	int num;
	cin>>num;
	if(Prime_Numbers(num))
	{
		cout<<"Yes"< 
假如一个数N是合数，它有一个约数a,a×b=N
 则a、b两个数中必有一个大于或等于根号N，一个小于或等于根号N。
 因此，只要小于或等于根号N的数（1除外）不能整除N，则N一定是素数。
 
 
通过数学推证，我们只需要从2跑到sqrt（n）就可以了！
 
这样代码运行速度就得到很大幅度的提升！
 
 
但总有人追求更快的运行速度，不过还真的可以优化再优化！！！
 
 
 首先我们要先理解一下——》孪生素数猜想(twin primes)
 
 
 
                                                                                                     (以上两张图片来自百度百科)
 
我们无需把 孪生素数猜想 理解透彻，
 
我们只需要知道——》大于3的素数只分布在6n-1和6n+1两数列中。（n非0自然数）
 
了解了这个猜想，我们就可以进行代码优化了
 
#include
#include
using namespace std;
bool Prime_Numbers(int x)
{
	if (x == 2 || x == 3)//将两个小数额外处理 
	{
		return 1;
	}
	if (x % 6 != 1 && x % 6 != 5)//不在6的倍数两侧的一定不是质数
	{
		return 0;
	}
	//在6的倍数两侧的数也不一定是质数
	int tmp = sqrt(x);
	for (int i = 5; i <= tmp; i += 6)
	{
		if (x % i == 0 || x % (i + 2) == 0)
		{
			return 0;
		}
	}
	//排除所有剩余的是素数
	return 1;
}

int main()
{
	int num;
		cin >> num;
		if (Prime_Numbers(num))
		{
			cout << "Yes" << endl;
		}
		else
		{
			cout << "No" << endl;
		}
	return 0;
}
 
是不是感觉代码边长了很多？
 
但速度也真真实实变快了很多！！！
 
注意：
 
在6的倍数的两侧的数，不一定是素数（比如6*6的左侧——》35就不是素数）！
 
一定要明白必要条件与充要条件的区别！！！
 
所以我们还是要跑个循环，但这次我们是 i+=6 ，不再是单纯无脑的i++了（这也是速度提升的关键）。
 
当然我们也不要忘记单独判断一下 2 与 3这两个素数。
 
 
如果这篇文章对您有帮助，请留下您免费的赞，这是对我最大的帮助！
 
也希望大佬们进行纠错与指点，我定会虚心接受！
 
 
在最后，
 
再次感谢您的阅读！