Pagini recente » Cod sursa (job #3032665) | Cod sursa (job #3003434) | Cod sursa (job #1804982) | Cod sursa (job #600459) | Cod sursa (job #1113911)
#include <cstdio>
using namespace std;
bool test[1005];
int sieve[1005], count;
void get_sieve() {
sieve[1] = 2;
count = 1;
test[2] = true;
for(int i = 3; i <= 1000; i+=2)
if( !test[i] ) {
for(int j = i * i; j <= 1000; j+= i)
test[j] = true;
sieve[++count] = i;
}
}
int get_primes(int N) {
int i = 1, ret = N;
while (sieve[i] * sieve[i] <= N && i <= count) {
if (N % sieve[i] == 0) {
while (N % sieve[i] == 0)
N /= sieve[i];
ret = ret / sieve[i] * (sieve[i] - 1);
}
i++;
}
if (N > 1)
ret = ret / N * (N - 1);
return ret;
}
int main() {
freopen("fractii.in", "r", stdin);
freopen("fractii.out", "w", stdout);
get_sieve();
int N;
scanf("%d", &N);
long long rez = 1;
for(int i = 2; i <= N; i++)
rez += 2 * get_primes(i);
printf("%lld", rez);
return 0;
}