Pagini recente » Cod sursa (job #2808999) | Cod sursa (job #586275) | Cod sursa (job #1094210) | Cod sursa (job #3194236) | Cod sursa (job #644689)
Cod sursa(job #644689)
// infoarena 1.0 - fractii
#include <fstream>
using namespace std;
char sir[1000001];
int t[1000001];
int main()
{
long int n,i,j,q;
long long c=1;
ifstream f("fractii.in");
ofstream g("fractii.out");
f>>n;
t[1]=1;
for(i=2;i<=n;i++)
{
if(sir[i]==0)
{
t[i]=i-1;
if(i<=n/i+1)
for(j=i*i; j<=n; j*=i)
t[j]=t[j/i]*i;
for(j=i*2; j<=n; j+=i)
{
sir[j]=1;
for(q=i; q<=n && j%q==0; q*=i)
if(!t[j] && (j/i)%q!=0)
t[j]=t[q]*t[j/q];
}
}
c+=2*t[i];
}
g<<c<<"\n";
f.close();
g.close();
return 0;
}