关于线性筛法实现欧拉函数
  • 板块学术版
  • 楼主wuhupai
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/4/10 20:11
  • 上次更新2023/10/23 18:47:47
查看原帖
关于线性筛法实现欧拉函数
544310
wuhupai楼主2023/4/10 20:11
void init(int n) {
	phi[1]=1;
	for(int i=2;i<=n;i++) {
		if(!use[i]){
			cnt++;
			prime[cnt]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=cnt;j++){
			if(i*prime[j]>n) break;
			use[i*prime[j]]=1;
			if(i%prime[j]==0){
				phi[i*prime[j]]=phi[i]*prime[j];
--------------->break;
			}
			phi[i*prime[j]]=phi[i]*(prime[j]-1);
		}
	}
}

中箭头指向的这个break是如何保证phi的正确性的

2023/4/10 20:11
加载中...