Cerc 6 2018 lectia 2
Lectie
Descompunerea in factori primi
O implementare a acestei probleme de complexitate O(sqrt(n)):
#include <stdio.h>
int main() {
int n, div, exp;
scanf("%d", &n);
div = 2; //Incepem cautarea factorilor primi de la primul numar prim
while ( div * div <= n ) { //Cautam factorii primi pana la radicalul lui n
exp = 0;
while ( n % div == 0 ) {
n /= div;
exp++;
}
if (exp > 0)
printf("%d^%d\n", div, exp);
div++;
}
// daca n mai contine un factor, el este un numar prim la puterea unu
if ( n > 1 )
printf( "%d^1\n", n );
return 0;
}Numarul de divizori si suma divizorilor
Fie descompunerea unui numar n in factori primi:
Numarul de divizori va fi:
Suma divizorilor:
Vezi demonstratia matematica a formulelor in caiet
Studiu de caz Problema divmul - infoarena
In caiete
Ciurul lui Eratostene
Reamintim aici doar algoritmul studiat anul trecut:
char ciur[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 2; d * d <= n; d++ )
if ( ciur[d] == 0 ) // daca d este prim
for ( i = d * d; i <= n; i = i + d ) // vom marca numerele din d in d
ciur[i] = 1;Varianta usor optimizata
Pentru un numar d prim, vom marca toti multiplii acestuia, nepari Ex: pentru d = 7, marcam multiplii: 7*7, 7*9, 7*11...sarind peste 7*8, &*10...
char ciur[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 4; d <= n; d += 2 )
ciur[d] = 1;
for ( d = 3; d * d <= n; d+= 2 )
if ( ciur[d] == 0 ) // daca d este prim
for ( i = d * d; i <= n; i = i + 2 * d ) // vom marca numerele din 2d in 2d
ciur[i] = 1;Putem de asemenea sa optimizam si memoria folosita, pastrand valorile ciurului doar pentru elementele impare.
ciur[1] va retine daca 3 e prim ciur[2] va retine daca 5 e prim ciur[3] va retine daca c7 e prim ciur[d/2] va retine daca d e prim Adica: ciur[k] va retine daca 2k + 1 e prim
char ciur[2000000];
for ( d = 3; d * d <= n; d+= 2 )
if ( ciur[d/2] == 0 ) // daca d este prim
for ( i = d * d; i <= n; i = i + 2 * d )
ciur[i/2] = 1;Utilizarea Ciurului lui Eratostene
Calcului numarului de divizori
Putem modifica modul de parcurgere al vectorului pentru a calcula numarul de divizori pentru numerele de la 1 la n:
int num_div[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 1; d <= n; d++ )
for ( i = d; i <= n; i = i + d )
num_div[i]++;Calcului sumei divizorilor
De asemenea putem calcula similar suma divizorilor pentru numerele de la 1 la n:
int sum_div[2000000];
...
fscanf( fin, "%d", &n );
for ( d = 1; d <= n; d++ )
for ( i = d; i <= n; i = i + d )
sum_div[i] = sum_div[i] + d;Nu uitați:
- Vectorul ciur[] este de tip caracter și nu întreg!
- În final vectorul ciur[i] este 0 dacă numărul este prim sau 1 în caz contrar.
Complexitate? Matematica este complexă, dar rețineți că metoda este aproximativ O(n) pentru valorile lui n cu care vom lucra noi. Pentru cei interesați, complexitatea este de fapt O(n∙log log n).
