质数

就是大于一的自然数，除了1和其本身外无其他约数的数如：3 、5、7…等其他的叫合数
下面我将为大家分享许多判断质数以及筛质数的方

一、质数的判断

1.暴力判断 时间复杂度:(O(n));

bool Judge_Prime( int num )
{
    if(num < 2 ) return false;
    for(int i = 2; i < num; i++)
      if( num % i == 0 )
         return false ;
    return true ;
}

这是我们最常见的判断方式

2.对暴力判断法的改进 时间复杂度:(O(sqrt(n)));

没有使用 i*i<=num 的原因是当i的值很大时可能会爆int，所以这个方法不是很保险，所以就没有写出来

bool Judge_Prime( int num )
{
     if(num < 2) return false;
     int num_1 = sqrt( num );
     for( int i = 2; i <= num_1; i++ )
        if(num % i == 0)
          return false ;
     return true ;
}

第二种方法的2.0版本 时间复杂度：O(sqrt(n)/2);

任一偶数一定能分解为2和其他偶数/奇数的积，因此一个数不能被2整除，那么这个数一定不能被其他偶数整除。利用这个特点，可以对方法2进行改进，判断数n能否被小于sqrt(n)的奇数整除。

bool Judge_Prime(int n) {
    if (n <= 3) {
        return n > 1;
    }
    if( n % 2 == 0) return false;
    //只需判断一个数能否被小于sqrt(n)的奇数整除
    int s = (int)sqrt(n);
    for (int i = 3; i <= s; i += 2) {
        if(n % 2 == 0 || n % i == 0 ) {
            return false;
        }
    }
    return true;
}

在上述代码中可以将 for(int i= 2;i <=num_1; i++)改成 for(int i= 2;i <=num/2; i++)但是相对来说，前一种方法更加的好。

3.孪生数法 时间复杂度:大概是前一种的三分之一即(O(sqrt(n)/3))：

因为大于等于5的质数一定和6的倍数相邻。例如5和7，11和13,17和19等等；下面是证明：

证明：令x≥1，将大于等于5的自然数表示如下：
······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······
可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友可以再另行了解一下，由于与我们主题无关，暂且跳过。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。
此时判断质数可以6个为单元快进，即将方法（2）循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被 6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6，每次判断循环变量k和k+2的情况即可

此证明来源于网络

bool Judge_Prime( int num )
{
    if(num==1 || num==0) return false;
    if(num ==2|| num==3 )
        return true ;
    //不在6的倍数两侧的一定不是质数
     if(num %6!= 1&&num %6!= 5)
         return false ;
    int tmp =sqrt( num);
    //在6的倍数两侧的也可能不是质数
    for(int i= 5;i <=tmp; i+=6 )
       if(num %i== 0||num %(i+ 2)==0 )
            return false ;
            //排除所有，剩余的是质数
                return true ;
}

4.试除法（Y总的） 时间复杂度：(O(sqrt(n)))

bool Judge_Prime(int num)
{
    if (num < 2) return false;
    for (int i = 2; i <= num / i; i ++ )
        if (num % i == 0)

            return false;
    return true;
}

这个俺就不讲了，可以购买算法基础课学习一波（doge

二、质数筛（就是三个筛法

1.朴素筛法 时间复杂度：(O(n*sqrt(n)))

#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int primes[N], cnt;
bool st[N];

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])
        {
            primes[cnt ++] = i;
        }
        for( int j = i + i; j <= n; j += i ) st[j] = true;
    }
 } 

int main()
{
    int n;
    cin>>n;

    get_primes(n);

    for(int i = 0; i < cnt; i ++) cout<<primes[i]<<" "; 
    return 0; 
}

2.埃氏筛法 时间复杂度：O(n*loglogn)

据Y老师所说是一个埃及人发明的（虽然我不相信

埃氏筛法原理：先将2到n范围内的所有整数写下来。其中最小的数字2是素数。将表中所有2的倍数都划去。
表中剩余的最小数字是3，它不能被更小的数整除，所以是素数。再将表中所有3的倍数都划去。
依次类推，如果表中剩余的最小数字是m时，m就是素数。然后将表中的所有m的倍数都划去。像这样反复操作，就能依次枚举n以内的素数。

#include<iostream>
#define N 1000010
#define ll long long

using namespace std;

int primes[N],cnt;
bool st[N];

void get_primes(int n)
{   
    for(int i=2;i<=n;i++)
    {
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}
int main()
{
    int n;
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    for( int i = 0 ; i < cnt ; i++)
    cout << primes[i] << ' ';
    return 0;
} 

3.线性筛法 时间复杂度：O(n)

核心代码

// 线性筛素数（以下把prime[j]这个数简写为pj）
// 如何保证线性:一个合数只能被筛掉一次
// 如何保证一个数字只被筛掉一次:这个数字只被它的最小质因数筛掉，当它的其他质因数想要筛掉它时，将无法进行筛除操作
void get_primes(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) primes[cnt++] = i; // 如果这个数字没有被记录，那么这个数字必然为素数，记录一下
        for (int j = 0; primes[j] <= n/i; ++j) {
            st[primes[j] * i] = true;  // 筛掉pj*i这个合数
            if (i % primes[j] == 0)  break; // i%pj==0，说明pj是i的最小素因子，因此i*素数的最小素因子也是pj，在i递增的时候也会被筛掉，因此不需要在这里判断
        }                
    }
}

纯净流代码

#include<iostream>
#define N 1000010
#define ll long long

using namespace std;

int primes[N],cnt;
bool st[N];

void get_primes(int n) {
    for (int i = 2; i <= n; ++i) {
        if (!st[i]) primes[cnt++] = i; 
        for (int j = 0; primes[j] <= n/i; ++j) {
            st[primes[j] * i] = true; 
            if (i % primes[j] == 0)  break; 
        }                
    }
}

int main()
{
    int n;
    cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    for( int i = 0 ; i < cnt ; i++)
    cout << primes[i] << ' ';
    return 0;

}