Вивести прості числа
Просте число – це натуральне число, яке має два дільники (1
і саме число).
Інакше кажучи, n > 1
– просте, якщо воно більше за 1
і ділиться без остачі на 1
та n
.
Наприклад, число 5
– просте, тому що воно не ділиться без остачі на 2
, 3
і 4
. Воно ділиться без остачі лише на 1
і на 5
.
Напишіть код, який виводить всі прості числа в діапазоні від 2
до n
.
Для n = 10
результат повинен бути 2,3,5,7
.
P.S. Код також повинен легко модифікуватися для будь-якого числа n
.
Є багато способів для розв’язання цієї задачі.
Скористаймося вкладеними циклами:
Для кожного `i` в інтервалі (від 2 до n) {
перевірити, чи число `i` має дільник з діапазону 2..i
якщо так => значення не просте
якщо ні => значення просте, показати його
}
Код з використанням мітки:
let n = 10;
nextPrime:
for (let i = 2; i <= n; i++) { // для кожного i...
for (let j = 2; j < i; j++) { // шукаємо дільник..
if (i % j == 0) continue nextPrime; // не просте, беремо наступне i
}
alert( i ); // просте число
}
Звичайно, цей код можна оптимізувати з точки зору продуктивності. Наприклад, ми могли б перевіряти всі j
від 2
до квадратного кореня з i
. Але все ж таки, якби потрібно було перебирати справді великі числа, нам прийшлося б використовувати просунуту математику і складні алгоритми на кшталт квадратичного решета чи методу решета числового поля.