infoarena

Aici puteţi discuta despre problema Dk (http://infoarena.ro/problema/dk).

Voi cum ati rezolvat problema? Eu m-am bazat pe niste lucruri care nu sunt garantate in enuntul problemei...

Exista vreun algoritm care sa se incadreze in timp si pentru 400 000 de numere prime distincte?

Exista un algoritm probabilistic numit Miller Rabin. Se gaseste si in Cormen la capitolul de Teoria numerelor.

Interesant.. eu ma folosisem de algortimul lui Fermat, dar vad ca asta e mai putin probabil sa dea rezultate gresite. O sa implementez si asa, mersi!

Poti precalcula numerele compuse care iti ies prime cu ce-ai facut si sa cauti binar dup-aia. pentru bazele 2, 3, 7 sunt 700 numere ...

e teorema lui fermat, nu algoritmul  :)

salutare... am  si eu o intrebare.. am rezolvat problema cu algoritmul miller - rabin si ptr 7 baze iau 80 cu TLE, ptr 6 baze  90 cu TLE si ptr 5 baze deja 70 cu TLE si incorect  :-k bazele le generez aleator cu o functie random, nu e totusi ceva mai optim ? mersi :)

Incearca baze numere prime. eu am folosit 2 3 5 7 si am luat 100

Bazele 2, 7 si 61 dau 100% rezultatul corect pentru numere mai mici ca 10^9.

S-a facut o reevaluare la aceasta problema.

si daca aplic ciurul lui eratostene, si dupa citesc fiecare element, verific daca e prim, si daka e, incrementez ceva...daka ati putea sa imi dati un contra exemplu... :peacefingers:

pana la un miliard sunt muuulte numere prime :) cum te-ai gandit sa le stochezi?

dar zice ca n<=400.000 ...deci nu cred ca ar fi o problema in a genera ciurul...

Dar mai zice si ca


deci tu ar trebui sa faci ciurul pana la 10⁹.

daca folosesc ciurul 8) ...as lua ceva puncte la problema asta  :'( ? si nu inteleg dc imi da Killed by signal  :annoyed:

In C/C++ elementele unui tablou unidimensional de N elemente sunt indexate de la 0 la N-1. Sa zicem ca tabloul este numit T, daca este accesat T[N], in linux, este returnat semnalul 11.

Am si eu cateva intrebari(si observatii) legate de aceasta problema
1) inainte sa pun conditia daca Nr e 1 atunci fals luam 20p, dupa am ajuns la 90
2) trebuie parsata citirea ? inainte sa parsez luam TLE pe 7 teste. Cu parsare scot max 1.8sec. Totusi ar mai trebui optimizat algoritmu sa intre si fara parsare?
3) E ceva special la testul 1 ? Nu-l iau de nici o culoare :) 
edit: am gasit, pe 2 il vedea ca nr compus lol...

mika era sa-ti dau dreptate :D... ca de ce daca nu iau 1 in considerare iau decat 20. Chestia e ca testele la care luam WA contineau pe 1:)) :fighting: :fighting: :fighting: :fighting:

Am incercat sa folosesc alogritmul baza pe Teorema lui Fermat si ceea ce trebuia sa verific era daca  (a^n -a)%n==0 -- unde a=numarul ales la intamplare 1>a>n; iar n numarul pe care il verificam.  Problema este ca daca avem de ex. n=200 si a= 50, atunci 50^200 devine cam greu de calculat fara sa iesi din memorie :D. Presupun ca iti poti da seama daca (a^n -a)%n==0  fara sa calculezi, dar nu prea stiu cum :sad:

Daca stii cat este restul impartirii lui a la n, atunci poti afla si restul impartirii lui a ^ n la n, ridicand la putere in timp logaritmic.

Folosesc algoritmul probabilistic numit Miller Rabin si iau TLE pe 6 teste ( cu ridicare la putere in timp logaritmic pentru bazele 2,7 si 61 ) . Ce as mai putea optimiza? Multumesc anticipat!

Am reusit in cele din urma, dar cred ca ar trebui marita limita de timp macar pana la 1 sec, oricum in O(n*sqrt(Xi)) nu intra .

Am si eu o intrebare : ce gresesc la rezolvare de imi da cu orice baza asi alege 30p?

Cred ca ar trebui marita limita de timp la aceasta problema.

Iau TLE pe un test folosind algoritmul lui Miller-Rabin cu 3 baze, ridicare la putere in timp logaritmic si parsarea citirii.

Fa decat cu doua baze

Iau 90p cu WA pe primul test in conditiile in care am parsat citirea, am implementat MillerRabin folosind 2 baze ( 2, 61 ). Poate cineva sa-mi spuna unde gresesc sau daca testul 1 are ceva special?

Poate iti pica testul 1 pt ca 1 nu e prim :)

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

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.

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. :)

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

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

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  :D