素数筛选

杨鹏伟

发布于 2020-09-10 16:06:10

1.1K00

代码可运行

文章被收录于专栏：ypwypw

运行总次数：0

代码可运行

所谓素数，就是除了一跟本身不能被奇因子整除

那么就直白的思路就是

bool isp(int x){
	if(x<2) return false
	else{
		for(int i=2;i*i<x;i++){
			if(!(x % i))
			return false;
		}
	}
	return true;
}

此种只适用与平时水题，n比较小的!

那么我们来看一种比较高效的思维

思路：我们知道素数的倍数肯定不是素数，所以的话，我们将素数的倍数置为1，经过这一系列处理后，遍历输出为0的即求出了N以内的所有素数！

for (int i=2;i<=n;i++)
    {
        if(!a[i])
        {
            for (int j=2*i;j<=n;j+=i)
                  a[j]=1;
        }
    }

这个其实还是可以优化的，仔细想想这里面有重复筛选的情况，比如6，它就是2*3，但是筛选的时候筛选了2次，因为它既是2的倍数，也是3的倍数。所以这个代码还可以进一步优化。

int pr[2000005];
void is_suu(int n)
{
    int m=sqrt (double(n+0.5));
    memset (pr,0,sizeof(pr));
    for (int i=2;i<=m;i++)
    {
        if(!pr[i])
        {
            for (int j=i*i;j<=n;j+=i)
                     pr[j]=1;
        }
    }
    for (int i=2;i<=n;i++)
          if(!pr[i])
        printf("%d ",i);
    printf("\n");
}

还有一种方法如下：（虽然不怎么明白原理）

int isPrime(int n)
{
    if(n<=1)
        return 0;
    if(n==2||n==3)
        return 1;
    if(n%6!=5&&n%6!=1)
        return 0;
    for(int i=5;i<=sqrt(n);i++)
        if(n%i==0||n%(i+2)==0)
        return 0;
    return 1;
}

这里一段完整的代码让大家运行感受下

#include<bits/stdc++.h>
#define N 100000
using namespace std;


/*
bool isp(int x){
	if(x<2) return false
	else{
		for(int i=2;i*i<x;i++){
			if(!(x % i))
			return false;
		}
	}
	return true;
}
*/
int pr[2000005];
void is(int n)
{
    int m=sqrt (double(n+0.5));
    memset (pr,0,sizeof(pr));
    for (int i=2;i<=m;i++)
    {
        if(!pr[i])
        {
            for (int j=i*i;j<=n;j+=i)
                     pr[j]=1;
        }
    }
    for (int i=2;i<=n;i++)
          if(!pr[i])
        printf("%d ",i);
    printf("\n");
}



int main(){
	int t;
	cin>>t;
	is(t); 
	
	return 0;
}