Подобряване на бързодействието при откриване на прости числа

Sieve of Eratosthenes
Sieve of Eratosthenes

Решето на Ератостен е алгоритъм за намиране на всички прости числа в интервала [1, n], където n е произволно естествено число. Алгоритъмът е кръстен на древногръцкия математик Ератостен, на когото е и приписано изобретяването му.

Тук е предложена програмна имплементация на езика C++ на нов по-бърз метод за откриване на прости числа, който превъзхожда Решето на Ератостен по бързодействие.

Търсят се простите числа до 1000000, като решението по метода на Решето на Ератостен е публикувано във файла 1.cpp а новия метод във файла 2.cpp (ще ви е необходим и класа timer.h), в резултат са дадени времената за изпълнение в милисекунди:

1.cpp = Time: 1931.95 ms
2.cpp = Time: 33.7718 ms

Прозиводителността е зашеметяваща 😉

Автор: Димитър Минчев

Доктор по информатика и компютърни науки

3 отговори на “Подобряване на бързодействието при откриване на прости числа”

  1. И двата кода изглеждат объркващо и кодирано, но не за това пиша- 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;

    Иначе- съвсем офтопик- кефя се на мерака и желанието което си личи от качените на сайта материали и искрено се надявам да продължавате да се занимавате с деца и да се видим в Шумен утре 🙂

Коментарите са изключени.