/*利用欧拉∮函数  n = n ( 1 - 1/p1) ( 1 - 1 / p2) ... ( 1 - 1/pn)*/
#include <stdio.h>
#include <iostream.h>
#include <fstream.h>
#include <memory.h>
#include <math.h>

#define SIZE 100000

bool prime[SIZE];

main (void)
{
#ifndef ONLINE_JUDGE
	freopen ("Relatives.txt","r",stdin);
#endif
	long i,j;

	memset (prime,true,sizeof (prime));
                // 这里筛选出SIZE内的所有素数
	for (i = 2;i < SIZE / 2;i++)
	{
		for (j = 2;j * i < SIZE;j++)
		{
			prime[i * j] = false;
		}
	}
	long double sum,n;
	long num;

	while (scanf ("%d",&num) != EOF && num != 0)
	{
		n = sqrt (num);
		sum = num;
		for (i = 2;i <= n;i++)
		{
			if (prime[i] && num % i == 0)
			{
				sum = sum * (i - 1) / i;
			}
		}
		if ((long)sum == num)
		{
			sum--;
		}
		printf ("%.0f\n",sum);
	}
	return 0;
}
或者帮我测下这几个数据，谢谢
1
2
3
99
1000000000
945881731
343598689
458586598
566588745
438969734
235565754
346767877
354657685
999999999
7
12
1
3
2
4
7
12
13
24
25
986797657
346565343
346568678
231223435
346467474
23
312443121
1000000000
0

• 终于过了！考虑质因子的时候出问题了！ (0) queyue2004 2005-05-08 11:57:08