Вступ
Ми купили велику коробку випадкових компʼютерних деталей на гаражному розпродажі.
Ми почали збирати ці деталі докупи, щоб будувати власні компʼютери.
Ми хочемо перевірити продуктивність різних комбінацій деталей, тож вирішуємо створити власну програму для бенчмаркінгу, щоб порівняти наші компʼютери між собою.
Обираємо відомий алгоритм «решето Ератосфена». Він стародавній, але має змусити наші компʼютери працювати на межі можливостей.
Вказівки
Створіть програму, яка реалізує алгоритм решета Ератосфена, щоб знайти всі прості числа, менші або рівні заданому числу.
Простим числом називають число, більше за 1, яке ділиться без остачі лише на 1 і на себе.
Наприклад, 2, 3, 5, 7, 11 і 13 - прості числа.
Натомість 6 - не просте число, бо ділиться не лише на 1 і на себе, а й на 2 і на 3.
Щоб скористатися решетом Ератосфена, спершу випишімо всі числа від 2 до заданого числа включно.
Далі виконаймо такі кроки:
- Знайдімо наступне непозначене число (пропускаючи позначені).
Це - просте число.
- Позначмо всі кратні цього простого числа як не прості.
Повторімо ці кроки, доки не пройдемо всі числа.
Наприкінці всі непозначені числа - прості.
Решето Ератосфена викреслює кратні кожного простого числа за допомогою додавання (багаторазово додаючи просте число) або множення (безпосередньо обчислюючи його кратні), а не перевіряючи кожне число на подільність.
Тести не перевіряють, чи ми реалізували саме цей алгоритм, лише те, чи отримали ми правильні прості числа.
Приклад
Припустімо, ми шукаємо прості числа, менші або рівні 10.
-
Випишімо 2, 3, 4, 5, 6, 7, 8, 9, 10, залишивши їх усі непозначеними.
2 3 4 5 6 7 8 9 10
-
2 непозначене, отже, воно просте.
Позначмо 4, 6, 8 і 10 як «не прості».
2 3 [4] 5 [6] 7 [8] 9 [10]
↑
-
3 непозначене, отже, воно просте.
Позначмо 6 і 9 як не прості (позначати 6 необовʼязково, адже його вже позначено).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
4 позначене як «не просте», тож пропускаємо його.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
5 непозначене, отже, воно просте.
Позначмо 10 як не просте (необовʼязково, адже його вже позначено).
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
6 позначене як «не просте», тож пропускаємо його.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
7 непозначене, отже, воно просте.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
8 позначене як «не просте», тож пропускаємо його.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
9 позначене як «не просте», тож пропускаємо його.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
-
10 позначене як «не просте», тож зупиняємося, бо більше немає чисел для перевірки.
2 3 [4] 5 [6] 7 [8] [9] [10]
↑
Ми розглянули всі числа й побачили, що 2, 3, 5 і 7 досі непозначені, а отже, вони й є прості числа, менші або рівні 10.
