筛选质数





题目:

输入一个正整数n,0<n,让n小于吧,判断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;
	}
}

总结:

时间复杂度是级别的,数据范围大时很不好用,但是思路简单。

方法二: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;



总结:

时间复杂度最小的算法,为O(n)。


全部评论

相关推荐

04-15 23:42
中山大学 Java
ResourceUtilization:过几天楼主就会捧着一堆offer来问牛友们该怎么选辣
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务