Pagini recente » Cod sursa (job #2400125) | Cod sursa (job #2737523) | Cod sursa (job #2737948) | Cod sursa (job #49371) | Cod sursa (job #1492278)
#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>
#include <cstring>
using namespace std;
struct prim{
int factor;
int putere;
};
vector <prim> factori;
ifstream in("fractii.in");
ofstream out("fractii.out");
bool *table;
void factori_primi(int x)
{
int p = 2;
prim a;
while(x!=1)
{
int nr = 0;
while(x%p==0)
{
nr++;
x/=p;
}
if(nr!=0)
{
a.factor = p;
a.putere = nr;
factori.push_back(a);
}
p++;
}
}
int indicator_euler(int x)
{
int indicator = 1;
for(unsigned int i=0;i<factori.size();i++)
indicator*=(factori[i].factor-1)*pow(factori[i].factor,factori[i].putere-1);
factori.clear();
return indicator;
}
void ciur_erastotene(int x)
{
int sqr = sqrt(x);
table = new bool[x+1];
memset(table,0,sizeof(bool)*(x+1));
for(int i=2;i<=sqr;i++)
{
if(!table[i])
{
for(int k = i*i;k<=x;k+=i)
table[k] = true;
}
}
}
int main()
{
int n;
in>>n;
in.close();
ciur_erastotene(n);
long long int nr_fractii = 1;
for(int i=2;i<=n;i++)
{
if(!table[i])
nr_fractii+=(i-1)*2;
else
{
factori_primi(i);
int indicator = indicator_euler(i);
nr_fractii+=indicator*2;
}
}
out<<nr_fractii;
out.close();
}