Quote:
Originally Posted by Redback
Most látom, elírtam. N=10-re kb 1 perc alatt kell lefutni. Sikerült megcsinálni, N=11-re 40 mp alatt fut le. Versenyen miért nem jutott így eszembe?!  |
Azt tanultam, hogy Eratoszthenész szitája a leggyorsabb ismert prímszám kereső algoritmus. Ha igazán gyorsat szeretnék írni N=10-re, akkor 10^10-nek a gyökéig előállítanám Eratoszthenész szitájával a prím számokat, majd az így megtalált prím számokkal osztogatnám végig a kérdéses intervallumokat. Ha többmagos a processzor, akkor természetesen több szálra tenném ezt a második lépést. Szerintem ez bőven belefér 1 percbe 10 jegy esetén.