第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-935 互质数个数

#include <stdio.h>
int main (void)
{
	int x;
	scanf("%d",&x);
	int i,res=x,mid=x;
	for(i=2;i*i<mid;i++)
	if(mid%i==0)
	{
		res=res/i*(i-1);
		while(mid%i==0) mid=mid/i;
	}
	if(mid>1)
	printf("%d",res/mid*(mid-1));
	else
	printf("%d",res);
	return 0 ;
}

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
 
int ans[100000];
int main()
{
    long long n;
    cin>>n;
    long long N=n;
    int pos=-1;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0) ans[++pos]=i;
        while(n%i==0) n=n/i;
    }
    if(n>1) ans[++pos]=n;
    int res=N;
    for(int i=0;i<=pos;i++)
    {
        res=res-res/ans[i];
    }
    cout<<res;
    return 0;
}

import java.io.*;
import java.math.*;
import java.util.*;


public class Main {

    static final int INF = 0x3f3f3f3f;
    static final long LNF = 0x3f3f3f3f3f3f3f3fL;


    public static void main(String[] args) throws IOException {
        initReader();
        int n=nextInt();
       int count=euler(n);
        pw.println(count);


        pw.close();
    }
    //直接求解欧拉函数
  static   int euler(int n){ //返回euler(n)
        int res=n,a=n;
        for(int i=2;i*i<=a;i++){
            if(a%i==0){
                res=res/i*(i-1);//先进行除法是为了防止中间数据的溢出
                while(a%i==0) a/=i;
            }
        }
        if(a>1) res=res/a*(a-1);
        return res;
    }


    static BufferedReader reader;
    static StringTokenizer tokenizer;
    static PrintWriter pw;

    public static void initReader() throws IOException {
        reader = new BufferedReader(new InputStreamReader(System.in));
        tokenizer = new StringTokenizer("");
        pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

    }

    public static boolean hasNext() {
        try {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
        } catch (Exception e) {
            return false;
        }
        return true;
    }

    public static String next() throws IOException {
        while (!tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

    public static String nextLine() {
        try {
            return reader.readLine();
        } catch (Exception e) {
            return null;
        }
    }

    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public static char nextChar() throws IOException {
        return next().charAt(0);
    }
}

n = int(input())
ans = n
i = 2
while i*i <= n:
    if n % i == 0:
        ans = ans // i * (i-1)
        while n % i == 0:
            n //= i
    i += 1
if n > 1:
    ans = ans // n * (n-1)
print(ans)