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);
	}

}