互质数的个数（一）
思路：欧拉函数。
题目链接
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);int t = sc.nextInt();while((t--)>0){long n = sc.nextLong();long ans = get_count(n);System.out.println(ans);}}public static long get_count(long n){if(n==1) return 1;long res = n;for(long i=2;i*i<=n;i++){if(n%i==0){res = res/i*(i-1);while(n%i==0) n/=i;}}if(n>1) res = res/n*(n-1);return res;}}
欧拉筛筛选素数
package com.Test.Demo.oj;import java.util.Scanner;public class Main{static int n,count;static boolean[] flag = new boolean[100010];static int[] p = new int[100010],p_min = new int[100010];public static void main(String[] args){Scanner sc = new Scanner(System.in);n = sc.nextInt();get_p(n);for(int i=0;i<count;i++)System.out.println(p[i]);}public static void get_p(int n){//欧拉筛 筛出2~n的素数for(int i=2;i<=n;i++){if(!flag[i]){p_min[i] = i;p[count++] = i;}for(int j=0;p[j]*i<=n;j++){flag[p[j]*i] = true;p_min[p[j]*i] = p[j];if(i%p[j]==0) break;}}}}
如果觉得《欧拉函数求互质数的个数》对你有帮助，请点赞、收藏，并留下你的观点哦！
