#include <vector>
...
vector<bool> c(N, true);//vector global
...
for(i = 2; i * i < N; i++) {
	if(c[i])//i prim
		for(j = i * i; j < N; j += i)//marchez multiplii sai
			c[j] = false;
}


Indicatorul lui (B)Euler

e(n) = nr de numere prime cu n mai mici ca n
e(7) = 6
e(6) = 2

formula: 
n = p1^a1 * p2^a2 * .. * pk^ak =>
e(n) = n * (p1 - 1) / p1 * (p2 - 1) / p2 * ... * (pk - 1) / pk

ex: 6 = 2 * 3 => e(6) = 6 * (2 - 1) / 2 * (3 - 1) / 3 = 6 / 6 * 1 * 2 = 2

for(i = 1; i <= n; i++)
	e[i] = i;
for(i = 2; i <= n; i++)
	if(e[i] == i)
		for(j = i; j <= n; j++)
			e[j] = e[j] / i * (i - 1);

FRACTII -> INFOARENA