Cod sursa(job #274550)
Utilizator | Data | 9 martie 2009 20:43:15 | |
---|---|---|---|
Problema | Ciurul lui Eratosthenes | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.4 kb |
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long phi[3000001];
int main()
{ long n,i,j;
freopen("ciur.in","rt",stdin);
freopen("ciur.out","wt",stdout);
scanf("%ld",&n);
for(i=1;i<=n+1;++i) phi[i]=i;
for(i=2;i<=n+1;++i)
if(phi[i]==i)
for(j=i;j+i<=n+1;j+=i)
phi[j]/=i,phi[j]*=(i-1);
printf("%ld",phi[n]);
//system("PAUSE");
return 0;
}