Решето на Ератостен е алгоритъм за намиране на всички прости числа в интервала [1, n], където n е произволно естествено число. Алгоритъмът е кръстен на древногръцкия математик Ератостен, на когото е и приписано изобретяването му.
Тук е предложена програмна имплементация на езика C++ на нов по-бърз метод за откриване на прости числа, който превъзхожда Решето на Ератостен по бързодействие.
Търсят се простите числа до 1000000, като решението по метода на Решето на Ератостен е публикувано във файла 1.cpp а новия метод във файла 2.cpp (ще ви е необходим и класа timer.h), в резултат са дадени времената за изпълнение в милисекунди:
1.cpp = Time: 1931.95 ms
2.cpp = Time: 33.7718 ms
Прозиводителността е зашеметяваща 😉
3 replies on “Подобряване на бързодействието при откриване на прости числа”
И двата кода изглеждат объркващо и кодирано, но не за това пиша- 1.cpp е сякаш злоумишлено забавен за да се получат некоректните резултати!
Вместо тази щуротия:
for(int j=2*i; j<N; j++)
if(j%i == 0) a[j] = 0;
всеки якичък състезател шестокласник знае, че идеята е самият цикъл да обходи само кратните на i:
for(int j=2*i; j<N; j+=i)
a[j] = 0;
Иначе- съвсем офтопик- кефя се на мерака и желанието което си личи от качените на сайта материали и искрено се надявам да продължавате да се занимавате с деца и да се видим в Шумен утре 🙂
Би било по-удобно ако кодът бе в самата стаития в блога. Иначе браво за резултатите!
Изключително добри резултати !