543 Dk

[•veleandu]

Poate iti pica testul 1 pt ca 1 nu e prim

[•AlexandruValeanu]

Nu, nu poate fi asta deoarece am pus conditie de iesire din functie puntru un numar <2.

[•SpiderMan]

Sunt numere relativ mici si s-ar putea ca testul de primalitate sa pice. Incearca pentru numere sa zicem < 10.000 sa faci testul in sqrt(N), s-ar putea sa mearga.

[•AlexandruValeanu]

Mersi mult pentru idee...am gasit una ceva mai eficienta cred eu: ciurul pana la 100000 si pentru orice peste Miller-Rabin....mersi inca o data pentru.

[•romircea2010]

eu am folosit bazele 2 si 29 si am luat 100 
ce-i drept a durat ceva pana sa-l gasesc pe 29 ca merge 

[•S7012MY]

Am citit articolul de pe wikipedia si nu inteleg de ce merge mai bine miller rabin decat fermat

[•romircea2010]

pai miller rabin se bazeaza pe mica teorema a lui fermat. chestia e ca daca numarul iese ca fiind prim pentru cateva baze sunt sanse mici ca el sa fie de fapt compus si aici intervine optimizarea din miller rabin: daca atunci vand faci exponentierea logaritmica gasesti o radacina netriviala a lui 1 atunci numarul este cu siguranta compus chiar daca respecta conditia micii teoreme a lui fermat. de exemplu numarul 561 respecta conditia micii teoreme a lui fermat chiar daca nu este prim (se divide cu 3) dar daca iei numarul 67 ca baza si incepi sa faci exponentierea prima data va trebui sa faci 67^2 pentru ca 561 - 1 = 560 este par si observi ca (67^2) % 561 == 1 deci ai gasit o radacina netriviala a lui 1 deci numarul este compus