判断素数/质数

#include <bits/stdc++.h>

using namespace std;

bool isprim(int a)
{
    if(a < 2) return false;
    //if(a == 2 || a == 3) return true;//判断2，3快一点，需要把i的初始值改为5
    for(int i = 2;i <= sqrt(a);++i)
        if(a % i == 0) return false;
    return true;
}

int main()
{
    for(int i = 0;i < 100;++i)
        if(isprim(i))
            cout << i << " ";
    return 0;
}

网上找了一圈发现了一个优化的点：即大于5的素数都在6的倍数的两侧，如5，6，7，5和7就是素数11，12，13，11和13就是素数，但是在6的倍数的两侧的不一定是素数，因此还需要判断一次

优化代码如下：

#include <bits/stdc++.h>

using namespace std;

bool isprim(int a)
{
    if(a < 2) return false;
    if(a < 6) return true;
    if(a%6 != 1 && a%6 != 5) return false;
    int sq = sqrt(a);//赋值防止多次调用sqrt函数
    for(int i = 5;i <= sq;i += 6)//要 % 6*k-1和6*k+1是因为所有素数的集合是6*k-1和6*k+1的子集(包含关系)，而非素数一定可以被素数整除
        if(a % i == 0 || a%(i+2) == 0) return false;//为什么要检查i+2，因为当i=5时5 = 6-1而i+2=6+1应该检查是否能被其他数检查
    return true;
}

int main()
{
    for(int i = 0;i < 100;++i)
        if(isprim(i))
            cout << i << " ";
    return 0;
}

优化后运行速度提升了一个档次