APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

C/C++线性筛素数的三种方法

2018年4月30日 1718点热度 4人点赞 0条评论

文章目录[隐藏]

  • 一、埃拉托斯特尼筛法
  • 二、欧拉筛法(线性筛法)
  • 三、一个奇怪的筛法

一、埃拉托斯特尼筛法

基本思想:素数的倍数一定不是素数

实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。

说明:整数1特殊处理即可。背过就好了。

时间复杂度O(nlogn)

空间复杂度为O(n)

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000001;
int vis[maxn];
void prime(int );


int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	prime(n);
	for(int i = 1;i <= m;++i){
		int x;
		scanf("%d",&x);
		if(vis[x]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
void prime(int n){
	for(int i = 0;i < n;++i) vis[i] = true;
	vis[0] = vis[1] = 0;
	for(int i = 2;i * i < n;++i) {
		if (!vis[i]) continue;
		for (int j = i; i * j < n; j++) vis[ i*j ] = 0;
	}
}

 

二、欧拉筛法(线性筛法)

时间复杂度O(n)

空间复杂度O(n)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> 
using namespace std;
void is_prime(int);

const int maxn(100001);
int prime[maxn];
bool vis[maxn];
int tot;

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	is_prime(n);
	for(int i=1;i<=m;++i){
		int x;
		scanf("%d",&x);
		if(vis[x]) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}


void is_prime(int list)
{
    memset(vis,true,sizeof(vis));
    vis[1]=false;
    for(int i=2;i<=list;++i){
        if(vis[i]) prime[++tot]=i;
        for(int j=1;j<=list&&i*prime[j]<=list;++j){
           vis[i*prime[j]]=false;
           if(i%prime[j]==0) break;
        }
    }
}

三、一个奇怪的筛法

时间复杂度 接近O(n)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream> 
using namespace std;

const int maxn(10000005);
bool he[maxn]; 
int n,m;

int main()
{
    scanf("%d%d",&n,&m);
    he[0]=he[1]=1;
    int t;
    for(int i=4;i<=n;i+=2) he[i]=1;
    for(int i=2;i<=n;i++)
        if(!he[i])
            for(int j=i*2;j<=n;j+=i)
                he[j]=1;
    for(int i=1;i<=m;i++){
        scanf("%d",&t);
        if(he[t]) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

 

洛谷:P3383

标签: C++ 洛谷
最后更新:2018年6月6日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
#不明觉厉#红芯浏览器,国产自主内核? waifu2x:开源的图片放大工具 #笔记#二进制与位运算 34.1G图片图包Ondrive/GDrive分流 LoveLive:μ's 43.6 G无损音乐歌曲分享 Yandex Money塑料实体万事达借记卡评测
标签聚合
C++ C/C++ OI HTML 洛谷 动漫 ST 日常
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang