назад до уроку

Вивести прості числа

важливість: 3

Просте число – це натуральне число, яке має два дільники (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. Але все ж таки, якби потрібно було перебирати справді великі числа, нам прийшлося б використовувати просунуту математику і складні алгоритми на кшталт квадратичного решета чи методу решета числового поля.