← All posts tagged CS

Goren

В projecteuler.net дошёл до 10ой задачи — это где надо найти сумму всех простых чисел меньше 2 миллионов. Я набыдлокодил следующий алгоритм: создал вектор, в этот вектор добавил число 2, а потом каждое следующее число проверял, делится ли оно на какое-либо число из вектора и, если ни на одно не делится, добавлял в вектор. Я использовал этот алгоритм для нахождения 10001ого простого числа в одной из предыдущих задач, весьма успешно, но чтобы проверить 2 миллиона чисел процесс застрял надолго. Писал на быдло-жабе, потому что меня на ней учили, но это не должно иметь значения. В дисклеймере Эйлер-проекта написано, что при правильно составленном алгоритме любая задача должна решаться на современном компе максимум за минуту, ну может на жабе будет две — у меня он застрял намертво, пока я не грохнул процесс. Таки шо, есть какой-то более оптимальный алгоритм нахождения всех простых чисел меньше какого-то предела, чем тот, что я описал?