首先我们要知道质数的概念：
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
知道了质数的概念，我们就可以大胆的说：“老师，我可以跑暴力”————》开个for循环从2怼到n-1，如果n被其整除那么就不是质数，反正是质数。
还是老话：“暴力解决不了所以问题，就比如时间上可能会很慢（因为你是在完全借助质数的定义跑循环）。”
所以要 优化！优化！ 优化！
#include<iostream>
#include<cmath>
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"<<endl;
}
else
{
cout<<"No"<<endl;
}
} 假如一个数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<iostream>
#include<cmath>
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这两个素数。
如果这篇文章对您有帮助，请留下您免费的赞，这是对我最大的帮助！
也希望大佬们进行纠错与指点，我定会虚心接受！
在最后，
再次感谢您的阅读！