Relatives

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 15708		Accepted: 7966

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.

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

7

12

0

6

4

 1 #include<iostream>

 2 #include<algorithm>

 3 using namespace std;

 4

 5 int ans;

 6

 7 void solve(int x)

 8 {

 9     ans = x;

10     int ant = 0;

11     for(int i = 2; i*i < x; i++)

12     {

13         if(x%i == 0)

14         {

15             ans = ans / i * (i - 1);

16         }

17         while(x%i == 0) x /= i;

18     }

19

20     if(x > 1)

21         ans = ans/x*(x-1);

22 }

23

24 int main()

25 {

26     int n;

27     while(1)

28     {

29         cin >> n;

30         if(n == 0)

31             break;

32         solve(n);

33         cout << ans << endl;

34     }

35

36

37     return 0;

38 }