游客 注册 | 登录
中文 | En

1065 - 互质

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 32 MB

给你一个正整数n，请问有多少个比n小的且与n互质的正整数？
两个整数互质的意思是，这两个整数没有比1大的公约数。

题目输入

输入包含多组测试数据。每组输入是一个正整数n（n<=1000000000）。当n=0时，输入结束。

题目输出

对于每组输入，输出比n小的且与n互质的正整数个数。

输入/输出样例

输入格式

7
12
0

输出格式

6
4

C语言解答

#include<stdio.h>

int eular(int n)
{
	int ret=1,i;
	for(i=2;i*i<=n;i++)
		if(n%i==0)
		{
			n/=i;
			ret*=i-1;
			while(n%i==0)
			{
				n/=i;
				ret*=i;
			}
		}
	if(n>1)
		ret*=n-1;
	return ret;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF,n)
		printf("%d\n",eular(n));
	return 0;
}

C++解答

#include<stdio.h>

int eular(int n)
{
	int ret=1,i;
	for(i=2;i*i<=n;i++)
		if(n%i==0)
		{
			n/=i;
			ret*=i-1;
			while(n%i==0)
			{
				n/=i;
				ret*=i;
			}
		}
	if(n>1)
		ret*=n-1;
	return ret;
}

int main()
{
	int n;
	while(scanf("%d",&n)!=EOF,n)
		printf("%d\n",eular(n));
	return 0;
}

Java解答

import java.util.Scanner;   
public class Main {   
 
static int eular(int n)
{
    int ret = 1,i;
    for (i = 2;i * i <= n;i++)
        if (n % i == 0)
        {
            n /= i;
            ret *= (i - 1);
            while (n % i == 0)
            {
                n /= i;
                ret *= i;
            }
        }
    if (n > 1)
        ret *= (n - 1);
    return ret;
}


 public static void main(String[] args) {   
    Scanner sc = new Scanner(System.in);   
   
    while(sc.hasNext()){
     int n=sc.nextInt();
     if(n==0) break;
     System.out.println(eular(n));
   }
  }
}
请先登陆