[C++知识库]C/C++判断是否为素数(最快)

质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数
常规解法，一层for循环从头开始遍历，小于sqrt(n)，如果n % i == 0那么则不是素数。

利用数学知识，所有的数都可以用
6n
6n+1
6n+2(3n+1)
6n+3(2n+1)
6n+4(3n+2)
6n+5
来表示，因为加括号的数肯定为素数，所以只需要判断6n+1和6n+5是否为素数，以及最初的1,2,3

#include <iostream>
#include <math.h>
using namespace std;

bool isPrime(int n){//判断素数
    if (n == 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 6 != 5 && n % 6 != 1) return false;
    for (int i = 5; i < sqrt(n); i+=6){
        //判断是否为奇数,使得算法更高效
        if (n % i == 0 || n % (i + 2) == 0) 
            return false;
    }
    return true;
}
int main()
{
	int n;
	cin>>n;
	if(isPrime(n))
	    cout<<n<<"是素数！"<<endl;
	else
	    cout<<n<<"不是素数！"<<endl;
	return 0;
}