#C240926E. 欧拉筛(噢)

标签（Label）

• 素数筛

• 欧拉函数

• 模板

网址（Website）

题目详情 - 【基础模板】素数筛法 - 求区间所有素数 - Super

题解 - 【基础模板】素数筛法 - 求区间所有素数 - Super

题目详情 - 【NOIP模板】欧拉函数 - 欧拉函数模板 - Super

题解 - 【NOIP模板】欧拉函数 - 欧拉函数模板 - Super

线性筛法 - OI Wiki 筛法求欧拉函数 - OI Wiki

练习题： #C240926B. GCD(波)

题目（Problem）

$\qquad$ 欧拉筛素数以及求欧拉函数。

代码（Code）

线性筛法

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define ull long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 2012345;

int pr[N],cnt,mx;
bitset<N> isnp;//is_not_prime
void Get_prime(){
	isnp[1] = 1;
	For(i,2,mx){
		if(!isnp[i]) pr[++cnt] = i;
		for(int j = 1; j<=cnt && pr[j]*i<=mx;j++){
			isnp[pr[j]*i] = true;
			if(i % pr[j] == 0) break;
		}
	}
}

signed main(){
	mx = rd();
	Get_prime();
	cout<<mx-isnp.count()<<'\n';
	For(i,1,mx){
		if(!isnp[i]) cout<<i<<' ';
	}cout<<'\n';
}

筛法求欧拉函数

#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define ull long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f;
const int N = 2012345;

int pr[N],phi[N],cnt,mx;
bitset<N> isnp;
void Get_prime(){
	phi[1] = isnp[1] = true;
	For(i,2,mx){
		if(!isnp[i]) pr[++cnt] = i, phi[i] = i-1;
		for(int j = 1; j<=cnt && pr[j]*i<=mx;j++){
			isnp[pr[j]*i] = true;
			if(i % pr[j] == 0){
				phi[i * pr[j]] = phi[i] * pr[j];
				break;
			}phi[i * pr[j]] = phi[i] * phi[pr[j]];
		}
	}
}

signed main(){
	mx = rd(),Get_prime();
	cout<<phi[mx]<<'\n';
    return 0;
}