UVA_Solution/10299.cpp at master · Mukit09/UVA_Solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<stdio.h>
#include<math.h>
#define si 40010

int a[si],pr[si],ll=1;
void sieve()
{
	int num=si-5,i,j,root;
	root=sqrt(num);
	a[1]=1;
	pr[ll++]=2;
	for(i=3;i<=num;i=i+2)
	{
		if(a[i]==0)
		{
			pr[ll++]=i;
			if(i<=root)
			{
				for(j=i*i;j<=num;j+=2*i)
					a[j]=1;
			}
		}
    }
}

int main()
{
	int i,n,l,p;
	double m,j;
	sieve();
	while(~scanf("%d",&n)&&n)
	{
		if(n==1||n==2)
		{
			printf("%d\n",n-1);
			continue;
		}
		l=sqrt(n);
		m=1;
		p=n;
		for(i=1;pr[i]<=l;i++)
		{
			if(p%pr[i]==0)
			{
				j=pr[i];
				m*=((j-1)/j);
				while(p%pr[i]==0)
					p/=pr[i];
			}
		}
		if(p>1)
		{
			j=p;
			m*=((j-1)/j);
		}
		m*=n;
		printf("%.0lf\n",m);
	}
	return 0;
}