Factorizarea numerelor

[•marin]

Ce complexitate are cel mai bun algoritm de descompunere a unui numar in factori primi?
Multumesc

[•devilkind]

sqrt(N) din cate stiu eu. Chiar si cu niste optimizari destul de bune, din cate stiu eu complexitatea ramane tot sqrt(N).

[•marin]

ce prompt esti
pai cum fac?
Multumesc

[•devilkind]

IeI toate numerele de la 1 pana la sqrt(n) si il imparti pe n la i atata timp cat n%i == 0. Daca la sfarsit n>1 atunci il mai pui si pe n^1 in descompunere. Poti sa optimizezi facand un ciur inainte si sa iei numai numerele prime in calcul.

[•Marius]

Ciurul consumă memorie.

Cod:

citește n;
D := mulțime vidă
e := 0
cât timp (n modulo 2) = 0 execută
    e := e + 1
    n := n / 2
sfcâtt
@adaugă lui D perechea (2, e) dacă e > 0
d := 3
cât timp (d * d <= n) execută         // (!)
    e := 0
    cât timp (n modulo d) = 0 execută
        e := e + 1
        n := n / d
    sfcâtt
    @adaugă mulțimii D perechea (d, e) dacă e > 0
    d := d + 2      // nu ai nevoie decât de numerele impare
sfcâtt
dacă (n > 1) atunci
    @adaugă mulțimii D perechea (n, 1)
sfdacă

// În D ai factorizarea lui n. O perechea semnifică un număr prim și puterea sa.

Dacă îmi aduc bine aminte, ar trebui să meargă. Complexitatea e clar O(N^1/2) datorită (!).