欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

备战NOIP——模板复习11

程序员文章站 2022-03-23 10:46:55
...

这里只有模板,并不作讲解,仅为路过的各位做一个参考以及用做自己复习的资料,转载注明出处。

素数筛

埃氏筛

/*Copyright: Copyright (c) 2018
*Created on 2018-11-02  
*Author: 十甫
*Version 1.0 
*Title: 埃氏筛
*Time: 3 mins
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int size = 100005;

bool prime[size];
inline void make(int n) {
	memset(prime, true, sizeof(prime));
	prime[1] = false;
	for(int i = 2;i <= n;i++) if(prime[i]) {
		for(int j = i * 2;j <= n;j += i) {
			prime[j] = false;
		}
	}
}

int main() {
	int n;
	scanf("%d", &n);
	make(n);
	int q;
	while(q--) {
		int k;
		scanf("%d", &k);
		printf("%d\n", prime[k]);
	}
	return 0;
}

欧拉筛

/*Copyright: Copyright (c) 2018
*Created on 2018-11-02  
*Author: 十甫
*Version 1.0 
*Title: 欧拉筛
*Time: 3.5 mins
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int size = 100005;

int prime[size];
bool flag[size];
inline void make_prime(int n) {
	for(int i = 2;i <= n;i++) {
		if(!flag[i]) {
			prime[++prime[0]] = i;
		}
		for(int j = 1;j <= prime[0] && prime[j] * i <= n;j++) {
			flag[prime[j] * i] = true;
			if(!(i % prime[j])) break;
		}
	}
}
int main() {
	int n;
	scanf("%d", &n);
	make_prime(n);
	for(int i = 1;i <= prime[0];i++) {
		printf("%d ", prime[i]);
	}
	printf("\n");
	return 0;
}

 

相关标签: 素数筛