Relatives 互質數個數

Relatives

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.

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

Sample Output

6

4

思路：

用歐拉定理的小于N的互質數個數：

首先，可以先了解一下費馬小定理：a^(p-1) ≡ 1 (mod p)

然後歐拉推廣得出：a^(φ(n))=1(mod n),其中n,a都為正整數且互質，φ(n)是小于n的數中，與n互質的數的個數。

如果n為質數，則φ(n)=n-1;

否則找出n的所有質因子：b1,b2,b3……bi;

φ(n)=n(1-(1/b1))(1-(1/b2))……（1-（1/bi)）

#include <iostream>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<stack>
#define INF 0x3f3f3f3f
#define me(a,b) memset(a,b,sizeof(a))
const int maxn=1e5+10;
using namespace std;

int main()
{
	int n,ans;
	while(scanf("%d",&n)!=EOF)
	{
		ans=n;
		if(n==0)
			break;
        for(int i=2;i*i<=n;i++)//n的因子隻存在在小于等于根号n的數中
		{
			if(n%i==0)//找到因子
			{
				ans=ans/i*(i-1);//套用上面所講公式，因怕資料太大，溢出，是以選擇先除再乘
			}
			while(n%i==0)//去掉n中所有等于i的因子
				n=n/i;
		}
		if(n>1)//說明n是質數
			ans=ans/n*(n-1);
		printf("%d\n",ans);
	}
    return 0;
}