P1174 互素

时间: 1000ms / 空间: 131072KiB / Java类名: Main

描述

对于某个数n,,我们这次的工作仅是求出小于n且和n互质的数的个数,,比如n=10时 1,3,7,9均与10互质

//互质的定义是gcd(a,b)=1

输入格式

输入只有一行，一个数N（1<=N<=2,000,000,000）。

输出格式

输出也只有一行，输出和小于n且和n互质的数的个数

测试样例1

输入

输出

----------------------------------------------------------------------------------------

* 欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n) 。

通式：φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。

-------------------------------------------------------------------------------------------------------------------

评测状态 Accepted

题目 P1174 互素

提交时间 2016-03-27 09:21:23

代码语言 Java

消耗时间 1325 ms

消耗内存 14288 KiB

----------------------------------------------------------------

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        Scanner sc=new Scanner(System.in);

        while(sc.hasNext()){

            int n=sc.nextInt();

            int i;

            int cnt=n;

            for(i=2;n!=1;i++){

                if(n%i==0){

                    cnt-=cnt/i;

                    while(n%i==0) n/=i;

                }

            }

            System.out.println(cnt);

        }

        sc.close();

    }

}