#include <iostream>
using namespace std;

const int MAX = 31624 + 10; //1000000000的平方根
bool nprime[MAX];
int prime[MAX];
int main()
{
	memset(nprime, 0, sizeof(bool)*MAX);
	int i, j;
	for(i = 2; i < MAX/2; i ++)
	{
		for(j = i*i; j < MAX; j += i)
              nprime[j] = true;
	}
	int c = 0;
	for(i = 2; i < MAX; i ++)
		if(!nprime[i])
		{		
		    prime[c ++] = i;
		}
	int n;
	while(cin >> n && n)
	{
		int ans = n;
		for(i = 0; i < c; i ++)
		 {
			if(n%prime[i] == 0)
			{
				ans /= prime[i];
				ans *= prime[i] - 1;		
			}
		 }
		 if(ans == n)
			 ans = n - 1;
		 cout << ans << endl;
	}
	return 0; 
}    

• 自己定一个 (731) xiaxia 2006-02-28 16:44:43
  • 999999986 你的程序得多少？ (0) frkstyc 2006-02-28 16:48:49
    • 499999993 对不 谢谢 (0) xiaxia 2006-02-28 16:50:44
      • 499999992 (0) frkstyc 2006-02-28 16:51:49
        • 万分感谢 我是猪头阿 ~~~~　啊啊啊啊　 (0) xiaxia 2006-02-28 16:55:42
• 最后如果有一个很大的素数，超过sqrt(10^9)的你没考虑到 (731) flymouse 2007-07-24 18:25:17
• Re:为什么老wa 大家看看 欧拉函数的 (731) 272549164 2008-07-23 20:33:50