筛选质数

题目：

输入一个正整数n，0<n,让n小于 $10^{9}$ 吧，判断n是否是质数

方法一：试除法（最简单）

分析：

用for(int i=2;;)来从2到n遍历，如果n能被i整除，就不是质数。

代码：

bool zhi_1(int n)
{
    if(n==1)
	return 0;
    for(int i=2;i<n;i++)
    {
        if(x%i==0)
	    return 0;
    }
    return 1;
}

优化：

因为因子都是成对出现，比如24，可以分成2 12，3 8，4 6；但我们只要判断它有没有较小的那个因数，如果没有，后面就不必判断。所以我们可以只让i<sqrt(n)。

代码：

bool zhi_2(int n)
{
	if(n==1)
		return 0;
	else if(n==2)
		return 1;
	else
	{
		int b=sqrt(x);
		for(int i=2;i<=b;i++)
		{
			if(x%i==0)
				return 0;
		}
		return 1;
	}
}

总结：

时间复杂度是 $\sqrt{n}$ 级别的，数据范围大时很不好用，但是思路简单。

方法二：6倍原理

分析：

对于所有的素数（除了2，3以外），都只有在6的倍数的左右两边有可能出现。一般要是数太大，导致要开很大的数组，就不用欧拉筛，总之就是在空间和时间之间抉择。

6倍原理的好处是可以判断一个数是否是质数，而欧拉筛是得出来的一组质数，要是判断单个数，用6倍原理。

代码：

bool zhi_3(int x)//目前已知最快的方法，相对方法2，节约三分之二时间，应该用这个就很少会超时吧。。 
{
	if(x==1)
		return 0;
	else if(x==2||x==3)//如果是2，3直接是素数
		return 1;
	if(x%6!=1&&x%6!=5)//如果不是6的倍数左右两边的数，就不是质数
		return 0;
	int b=sqrt(x);
	for(int i=5;i<=b;i+=6)//判断x能否被小于根号n的，在6的倍数两边的数整除
	{
		if(x%i==0||x%(i+2)==0)//能被整除就不是质数
			return 0;
	}
	return 1;
}

结论：

比前一个方法要判断的数据少了三分之二，但也不是最快的。

方法三：埃氏筛法

分析：

埃拉托斯特尼 (Eratosthenes) 筛法，简称埃氏筛或爱氏筛，为了得到自然数 n 以内的全部素数，必须把不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。给出要筛数值的范围 n，先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉;再用下一个质数，也就是 3 筛，把 3 留下，把 3 的倍数剔除掉;接下去用下一个质数 5 筛，把 5 留下，把 5 的倍数剔除掉;不断重复下去...

代码：

#include<iostream>
using namespace std;
const int N=1e9;//一般大于输入的n的上限
int n,sum=0，zhi[N];//sum记录质数的个数，zhi[]数组用来依次记录质数。
bool status[N];//记录每个数的状态，1代表不是质数，0代表是质数，刚开始都是0；
void pan(int n)
{
    status[1]=1;
    for(int i=2;i<=n;i++)//从2到n遍历
    {
        if(status[i]==0)//如果这个数字i是质数
            zhi[sum++]=i;//记录下来这个质数。
        for(int j=i*2;j<=n;j+=i)
            status[j]=1;//将质数的倍数记录为1，即不是质数。
    }
}
int main()
{
    scanf("%d",&n);
    pan(n);
    return 0;
}

优化：

因为偶数里面只有2是素数，所以我们可以只去将质数的倍数排除掉就行。，即将里面的for循环拉到if语句里。

代码：

#include<iostream>
using namespace std;
const int N=1e9;//一般大于输入的n的上限
int n,sum=0，zhi[N];//sum记录质数的个数，zhi[]数组用来依次记录质数。
bool status[N];//记录每个数的状态，1代表不是质数，0代表是质数，刚开始都是0；
void pan(int n)
{
    status[1]=1;
    for(int i=2;i<=n;i++)//从2到n遍历
    {
        if(status[i]==0)//如果这个数字i是质数
        {
            zhi[sum++]=i;//记录下来这个质数。
            for(int j=i*2;j<=n;j+=i)
                status[j]=1;//将质数的倍数记录为1，即不是质数。
        }
    }
}
int main()
{
    scanf("%d",&n);
    pan(n);
    return 0;
}

总结：

复杂度为nloglogn，应该仅次与欧拉筛法。这个筛数的思路也很好。

方法四：欧拉法/线性筛数法（我已知的里，最快的）

分析：

在埃氏筛法中，对于6这个数，我们发现它被2，3，都枚举了一次，这样造成了时间的浪费，欧拉筛就在此进行改进。让每个合数只被它的最小质因子筛选一次。

代码：

#include<iostream>
using namespace std;
const int N=1e9;//一般大于输入的n的上限
int n,sum=0，zhi[N];//sum记录质数的个数，zhi[]数组用来依次记录质数。
bool status[N];//记录每个数的状态，1代表不是质数，0代表是质数，刚开始都是0；
void pan(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(states[i]==0)
            zhi[sum++]=i;//记录质数
        for(int j=0;i*zhi[j]<n;j++)
        {
            status[zhi[j]*i]=1;
            if(i%zhi[j]==0)//zhi[j]就是i的最小质因子，跳出循环
                break;
        }
    }
}
int main()
{
    scanf("%d",&n);
    pan(n);
    return 0;