Acwing---874. 筛法求欧拉函数 (Java)_分解质因数模板
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Acwing---874. 筛法求欧拉函数 (Java)_分解质因数模板,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2301字,纯文字阅读大概需要4分钟。
内容图文
![Acwing---874. 筛法求欧拉函数 (Java)_分解质因数模板](/upload/InfoBanner/zyjiaocheng/604/48a4c936fca447a38b6a5c23ca89a385.jpg)
874. 筛法求欧拉函数
①. 题目
②. 思路
欧拉函数是一个 积性函数 就是说 m,n互素 则 φ(mn)=φ(m)?φ(n)
- ①若该数是质数p的话,那么该数的欧拉函数就是p?1。
- ② 筛法利用的原理是 任意整数 x 的倍数 2x,3x,… 等都不是质数 ,但是即便如此也会有重复标记的现象,例如12既会被2又会被3标记,在标记2的倍数时,12=6?2
,在标记3的倍数时,12=4?3 ,根本原因是没有找到唯一产生12的方式。 - ③ p不是质数的时候 用最小的素因子去计算
- ③ 若i%primes[j]==0,由于primes[j]是i的一个质因子,φ(primes[j]×i)=primes[j]×φ(i)。
- ④ 若i%primes[j]!=0,primes[j]就一定是primes[j]×i的最小质因子,可以得到φ(primes[j]×i)=φ(i)×(primes[j]?1)。
③. 学习点
筛选质数法
④. 代码实现
暴力解法
import java.util.Scanner;
public class _874_筛法求欧拉函数_暴力 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextInt();
long res=0;
for(long i=1;i<=n;i++) {
long tmp=i;
long tmp2=i;
for(long j=2;j<=Math.sqrt(tmp2);j++) {
if(tmp2%j==0) {
while(tmp2%j==0) {
tmp2/=j;
}
tmp=tmp/j*(j-1);
}
}
if(tmp2>1) {
tmp=tmp/tmp2*(tmp2-1);
}
res+=tmp;
}
System.out.println(res);
}
}
筛选法优化欧拉函数求和
import java.util.*;
public class Main {
/*
* ② 若该数是质数p的话,那么该数的欧拉函数就是p?1。
* ④ 若i%primes[j]==0,由于primes[j]是i的一个质因子,所以φ(primes[j]×i)=primes[j]×φ(i)。
* ⑤ 若i%primes[j]!=0,primes[j]就一定是primes[j]×i的最小质因子,
* 可以得到φ(primes[j]×i)=φ(i)×(primes[j]?1)。
*/
static int N=1000010;
static int[] phi=new int[N]; //存储数字i的欧拉函数
static int[] primes=new int[N]; //存储质数的下标对应的质数
static int cnt=0;
static boolean[] st=new boolean[N]; //表示n有没有被筛选掉
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
phi[1]=1;
for(int i=2;i<=n;i++) {
//判断是否为质数
if(!st[i]) {
primes[cnt++]=i;
phi[i]=i-1; //i是质数,那么该数的欧拉函数就是i?1。
}
for(int j=0;primes[j]<=n/i;j++) {
st[primes[j]*i]=true; //筛选掉质数的倍数
//若i%primes[j]==0,由于primes[j]是i的一个质因子,所以φ(primes[j]×i)=primes[j]×φ(i)。
if(i%primes[j]==0) {
phi[primes[j]*i]=primes[j]*phi[i];
break;
}
//若i%primes[j]!=0,primes[j]就一定是primes[j]×i的最小质因子,
* //可以得到φ(primes[j]×i)=φ(i)×(primes[j]?1)。
phi[primes[j]*i]=(primes[j]-1)*phi[i];
}
}
//将所有的欧拉函数和加起来
long res=0;
for(int i=1;i<=n;i++) {
res+=phi[i];
}
System.out.println(res);
}
}
内容总结
以上是互联网集市为您收集整理的Acwing---874. 筛法求欧拉函数 (Java)_分解质因数模板全部内容,希望文章能够帮你解决Acwing---874. 筛法求欧拉函数 (Java)_分解质因数模板所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。