Java实现 蓝桥杯 算法提高 欧拉函数（数学）

试题 算法提高 欧拉函数

问题描述

　　老师出了一道难题，小酱不会做，请你编个程序帮帮他，奖金一瓶酱油：

　　从1—n中有多少个数与n互质?

　　|||||╭══╮ ┌═════┐

　　╭╯让路║═║酱油专用车║

　　╰⊙═⊙╯ └══⊙═⊙═(坑爹的题面格式化，害得我用‘|’来代替空格，复制到记事本上看就变成正版的了)

输入格式

　　输入共一行，表示一个整数n。

输出格式

　　输出共一行，表示从1—n中与n互质的数的个数。

样例输入

30

样例输出

8

数据规模和约定

　　60%的数据≤10^6

　　100%的数据≤2*10^9

PS：

这个题先附上暴力代码，只能过90的分，后面有大佬的欧拉函数的解法

import java.util.ArrayList;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        sc.close();

        ArrayList<Integer> list = new ArrayList<Integer>();

        int temp = n;

        for (int i = 2; temp != 1; i++) {

            if (temp % i == 0) list.add(i);

            while (temp % i == 0) {

                temp /= i;

            }

        }

        int count = 0;

        //   System.out.println(list);

        boolean[] bool = new boolean[n];

        for (int i : list) {

            int index = 1;

            while (index * i < n) {

                bool[index * i] = true;

                index++;

            }

        }

        for (int i = 1; i < n; i++) {

            if (!bool[i]) {

                count++;

            }

        }

//        A:

//        for (int i = 1; i < n; i++) {

//            for (int j : list){

//                if(i % j == 0){

//                    continue A;

//                }

//            }

//            count++;

//        }

        System.out.println(count);

    }

}

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);

        int n = in.nextInt();

        long ans = n;

        for (int i = 2; i * i <= n; i++) {//优化 O(sqrt(n)) 不过要在出口 if(n>1)ans/n*(n-1) O(n)不用

            if (n % i == 0) {

                ans = ans / i * (i - 1);////n*(1-(1/p))转化为n/p*(p-1)

                while (n % i == 0)

                    n /= i;

            }

        }

        if (n > 1)

            System.out.println(ans / n * (n - 1));

        else

            System.out.println(ans);

    }

}