Pagini recente » Cod sursa (job #191652) | Cod sursa (job #554602) | Cod sursa (job #1032849) | Cod sursa (job #1098034) | Cod sursa (job #2047583)
#include <stdio.h>
using namespace std;
bool verifPrim[1000001];
int prime[78499];
int main(){
freopen("fractii.in","r",stdin);
freopen("fractii.out","w",stdout);
int n,k=1,i,j,ci;
long long nr_fractii_tot,nr_fractii;
scanf("%d",&n);
prime[1] = 2;
for(i=3;i<=1000000;i+=2){
if(verifPrim[i] == 0){
prime[++k] = i;
j=3;
while(i*j<=n){
verifPrim[i*j] = 1;
j+=2;
}
}
}
nr_fractii_tot = 1;
for(i=2;i<=n;i++){
ci = i;
j=1;
nr_fractii = i;
while(ci != 1){
if(ci%prime[j] == 0){
while(ci%prime[j] == 0){
ci /= prime[j];
}
nr_fractii /= prime[j];
nr_fractii *= prime[j]-1;
}
j++;
}
nr_fractii_tot += nr_fractii*2;
}
printf("%lld",nr_fractii_tot);
return 0;
}