infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: Mari n din Noiembrie 01, 2008, 17:20:40


Titlul: Factorizarea numerelor
Scris de: Mari n din Noiembrie 01, 2008, 17:20:40
Ce complexitate are cel mai bun algoritm de descompunere a unui numar in factori primi?
Multumesc

Titlul: Factorizarea numerelor
Scris de: Savin Tiberiu din Noiembrie 01, 2008, 17:46:03
sqrt(N) din cate stiu eu. Chiar si cu niste optimizari destul de bune, din cate stiu eu complexitatea ramane tot sqrt(N).

Titlul: Factorizarea numerelor
Scris de: Mari n din Noiembrie 01, 2008, 17:51:55
ce prompt esti :)
pai cum fac?
Multumesc

Titlul: Factorizarea numerelor
Scris de: Savin Tiberiu din Noiembrie 01, 2008, 23:11:57
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.

Titlul: Răspuns: Factorizarea numerelor
Scris de: Marius Stroe din Noiembrie 02, 2008, 12:15:19
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(N1/2) datorită (!).


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines