Утворення послідовності простих чисел
Будемо розглядати утворення простих чисел в межах від 2 до деякого заданого Х.
Спосіб 1. Пов’язаний з послідовним перебором натуральних чисел від 2 до Х. Для кожного з них реалізується тестування на простоту, і у разі позитивного результату чергове число переводиться у послідовність простих. У зв’язку з необхідністю тестування такий спосіб вважається не ефективним за витратами часу.
Спосіб 2. Спосіб відомий під назвою решето Ератосфена. Відповідний класичний алгоритм такий:
виписуємо всі натуральні числа від 2 до Х;
обводимо перше число 2, а всі інші, кратні 2, викреслюємо;
відшукуємо найменше необведене і не викреслене, обводимо його, фіксуємо його значення L, а після цього викреслюємо кожне L-те число, тобто всі, кратні йому;
п.3 повторюємо, поки не залишиться необведених і незакреслених чисел.
Всі обведені числа є простими. Спосіб не вимагає виконання арифметичних операцій, що і визначає його швидкодію. У зв’язку з необхідністю попереднього виписування всіх натуральних чисел, такий спосіб вважається теж не ефективним за витратами пам’яті.
Вдвічі зменшити витрати пам’яті дозволяє модифіковане решето Ератосфера. Воно відрізняється від класичного лише тим, що виписується 2 і всі непарні натуральні числа, які не перевищують Х. При цьому перше просте число 2 обводиться відразу.
Кількість отриманих простих чисел від 2 до Х є значенням, так званої, функції π(х), рівне кількості всіх простих чисел, що не перевищують Х.