同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

22354_Relatives

2022-5-16 18:21| 发布者: Hocassian| 查看: 18| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-5-89506349590400-Problem List-采集的数据-后羿采集器.html

Pro.ID

22354

Title

Relatives

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=22354

AC

Submit

Ratio

61.54%

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

Given n, a positive integer, how many positive integers less than n are relatively prime to n ? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.

输入

There are several test cases. For each test case, standard input contains a line with n ≤ 1,000,000,000. A line containing 0 follows the last case.

输出

Description

Input

There are several test cases. For each test case, standard input contains a line with n ≤ 1,000,000,000. A line containing 0 follows the last case.

Output

For each test case there should be single line of output answering the question posed above.

Sample Input

7
12
0

Sample Output

6
4

Source

Waterloo local contest 2002

样例输入