APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

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

2018年4月30日 2123点热度 13人点赞 1条评论

一、埃拉托斯特尼筛法

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

实现方法:用一个长度为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

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C++ 洛谷
最后更新:2018年6月6日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

  • ZXXS

    欧拉筛的定义是什么

    2022年10月9日
    回复
  • razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
    取消回复

    神楽坂 みずき

    萌萌萌,好萌!

    搜索
    最新 热点 随机
    最新 热点 随机
    站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版
    读 太宰治《人间失格》有感 waifu2x:图片放大效果 StickerMule1刀全球包邮Unixstickers贴纸评测 C/C++Manacher算法(字符串判断回文串) 马拉车算法 模板 #C/C++#裴蜀定理(貝祖等式) 动态规划(DP)方法学习
    标签聚合
    动漫 C++ C/C++ HTML 洛谷 ST 日常 OI
    分类
    • ACGN
    • Coding
    • Daily
    • DevOps
    • OI
    • Share

    COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

    Theme Kratos Made By Seaton Jiang