Вернуться к уроку

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

важность: 3

Натуральное число, большее 1, называется простым, если оно ни на что не делится, кроме себя и 1.

Другими словами, n>1 – простое, если при делении на любое число от 2 до n-1 есть остаток.

Создайте код, который выводит все простые числа из интервала от 2 до 10. Результат должен быть: 2,3,5,7.

P.S. Код также должен легко модифицироваться для любых других интервалов.

Схема решения

Для всех i от 1 до 10 {
  проверить, делится ли число i на какое - либо из чисел до него
  если делится, то это i не подходит, берем следующее
  если не делится, то i - простое число
}

Решение

Решение с использованием метки:

nextPrime:
  for (var i = 2; i <= 10; i++) {

    for (var j = 2; j < i; j++) {
      if (i % j == 0) continue nextPrime;
    }

    alert( i ); // простое
  }

Конечно же, его можно оптимизировать с точки зрения производительности. Например, проверять все j не от 2 до i, а от 2 до квадратного корня из i. А для очень больших чисел – существуют более эффективные специализированные алгоритмы проверки простоты числа, например квадратичное решето и решето числового поля.