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