Pagini recente » Cod sursa (job #1593506) | Cod sursa (job #639694) | Cod sursa (job #1035602) | Cod sursa (job #1165128) | Cod sursa (job #16159)
Cod sursa(job #16159)
#include <cstdio>
#define maxn 1<<20
bool t[maxn];
int primes[maxn], T;
int n;
void citire()
{
freopen("fractii.in", "r", stdin);
scanf("%d", &n);
}
void prim()
{
int i, j;
for(i=4;i<=n;i+=2) t[i]=1;
for(i=3;i<=n;i+=2)
if(!t[i])
{
for(j=i+i;j<=n;j+=i) t[j]=1;
}
for(i=2;i<=n;i++) if(!t[i]) primes[++T]=i;
}
int tot(int k)
{
int i, p=k/2;
double sum=k;
for(i=1;i<=T;i++)
{
if(primes[i]>p) break;
if(k%primes[i]==0)
{
sum=sum*((primes[i]-1.0)/(double)primes[i]);
}
}
if(sum==k) return (int) sum-1;
return (int) sum;
}
int main()
{
citire();
prim();
//printf("%d\n", tot(7));
long long sum=0;
//for(int i=2;i<=n;i++) sum+=(long long)tot(i);
sum*=2;
sum++;
freopen("fractii.out", "w", stdout);
printf("%lld\n", sum);
return 0;
}