Pagini recente » Cod sursa (job #3285965) | Cod sursa (job #1336667) | Cod sursa (job #1275684) | Cod sursa (job #328542) | Cod sursa (job #2061192)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("fractii.in");
ofstream g("fractii.out");
int div[1000005], n, i, j;
long long tot[1000005], sol;
void makeciur(int n)
{
for(int i = 2; i * i <= n; i++) if(!div[i])
for(int j = i * i; j <= n; j += i) div[j] = i;
}
void maketot(int n)
{
tot[1] = 1;
sol = 1;
for(i = 2; i <= n; i++)
{
if(!div[i]) tot[i] = i - 1;
else
{
int nr = i;
int pow = 0;
while(nr % div[i] == 0) nr /= div[i], pow++;
tot[i] = i / (nr * div[i]) * tot[nr] * (div[i] - 1);
}
sol += 2 * tot[i];
}
}
int main()
{
f >> n;
makeciur(n);
maketot(n);
g << sol << '\n';
return 0;
}