备战NOIP——模板复习11

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

素数筛

埃氏筛

/*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
", 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("
");
	return 0;
}