543 Dk

[•astronomy]

Aici puteţi discuta despre problema Dk.

[•Dastas]

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?

[•domino]

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

[•Dastas]

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!

[•bogdan2412]

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

[•gcosmin]

e teorema lui fermat, nu algoritmul 

[•floringh06]

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  bazele le generez aleator cu o functie random, nu e totusi ceva mai optim ? mersi

[•blasterz]

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

[•pauldb]

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

[•DITzoneC]

S-a facut o reevaluare la aceasta problema.

[•gabor_oliviu1991]

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

[•fireatmyself]

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

[•gabor_oliviu1991]

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

[•DITzoneC]

Dar mai zice si ca

1 ≤ X_i ≤ 10⁹

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

[•drag0s93]

daca folosesc ciurul ...as lua ceva puncte la problema asta  ? si nu inteleg dc imi da Killed by signal 

[•Prostu]

daca folosesc ciurul ...as lua ceva puncte la problema asta  ? si nu inteleg dc imi da Killed by signal 

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.

[•mika17]

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

[•Bogdan_tmm]

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

[•emilianparaicu14]

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 . Presupun ca iti poti da seama daca (a^n -a)%n==0  fara sa calculezi, dar nu prea stiu cum

[•toni2007]

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.

[•SebiSebi]

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 .

[•AlexandruValeanu]

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

[•repp4radu]

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.

[•misino]

Fa decat cu doua baze

[•AlexandruValeanu]

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?