Pagini recente » Cod sursa (job #2999501) | Cod sursa (job #1516463) | Cod sursa (job #2034523) | Cod sursa (job #2518788) | Cod sursa (job #120058)
Cod sursa(job #120058)
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
unsigned char prime[1000000];
long long int tot[1000000];
int main(int argc , char *argv[]){
long int i , j;
FILE *f , *g;
long long int nr=1;
long int n , power , aux;
prime[1]=1; // 1 if not prime , 0 if prime
tot[1]=1;
f=fopen("fractii.in" , "r");
g=fopen("fractii.out" , "w");
for(i=2 ; i < ((long int) sqrt(1000000)) ; i++){
if(! prime[i]){
for(j=i*2 ; j<1000000 ; j=j + i){
prime[j]=1;
}
}
}
fscanf(f , "%ld" , &n);
for(i=2 ; i <= n ; i++){ // all numbers 1 to n
if(! prime[i]){
tot[i]=i - 1;
nr=nr + (i - 1) * 2;
}
else{
j=1; //index in primes array
while(1){
if(i%j == 0 && ! prime[j]){
aux=i;
power=0;
while(aux % j == 0){
aux=aux / j;
power++;
}
tot[i]=tot[aux] * (j - 1)
* ((long int)pow(j , power - 1));
nr=nr + tot[i] * 2;
break;
}
j=j + 1;
}
}
}
fprintf(g , "%lld" , nr);
fclose(f);
fclose(g);
return 0;
}