Pagini recente » Cod sursa (job #2705800) | Cod sursa (job #1251074) | Cod sursa (job #1751926) | Cod sursa (job #1150103) | Cod sursa (job #2749885)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("fractii.in");
ofstream fout("fractii.out");
int n;
const int nmax = 1e6 + 1;
bitset<nmax> prime;
vector<int> fact[nmax];
int main()
{
fin >> n;
int i , j;
for(i=4;i<=n;i+=2 )
{prime[i] = 1;
fact[i].push_back(2);
}
fact[2].push_back(2);
for(i=3;i<=n;i+=2)
if(prime[i] == 0)
{ fact[i].push_back(i);
for(j=2*i;j<=n;j+=i)
{prime[j] = 1;
fact[j].push_back(i);
}
}
long long result = 0 , maxi = 1 , value = 1;
for(i=2;i<=n;++i)
{ int res = 1;
for(auto nr: fact[i])
{
int cp = i;
while(cp > 1 && cp%nr == 0)
{
cp /= nr;
res *= nr;
}
res /= nr;
res *= (nr - 1);
}
result += 1LL*2*res;
}
fout << result + 1;
return 0;
}