Верно ли условие задачи?

Question

[Alex Ozerov]

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

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

Например, 5 это простое число, оно не может быть разделено без остатка на 2, 3 и 4.

Напишите код, который выводит все простые числа из интервала от 2 до n.

Для n = 10 результат должен быть 2,3,5,7.
Обычная задача по js, но я тут подумал и заметил, что условие заставляет нас искать числа, при которых будет остаток при делении на 10 например. Ответ говорит что 2 3 5 7 правильно, но при делении на 2 и на 5 остатка нет, а нам же нужно выводить только числа у которых будет остаток. Обьясите пожалуйста

Comments

[Lynn «Кофеман»]

Нет. n в определении простоты чисел и n в условии задачи это разные вещи.

Если проще, то ищи все простые числа в интервале от 2 до k

[Alex Ozerov]

Алексей Тен, наконец, доперло. Благодарю.

Answer 1

[Karpion]

условие заставляет нас искать числа, при которых будет остаток при делении на 10 например

Условие ничего не заставляет. И Вы его неверно поняли.

"Вывести простые числа" - это "вывести такие числа, у которых при делении на меньшие есть остаток".

Надо ли проверять остаток при делении на десять? Нет, не надо. Потому что мы ранее проверили остаток при делении на пять и на два; и если хотя бы в одном случае остаток был - то он будет и при делении на десять.
Иными словами, надо проверять не "все меньшие числа", а только "все простые меньшие числа"; а для этого их надо сохранять в массиве.

Кроме того, деление на два обычно не проверяют, а просто пишут программу так, чтобы она перебирала нечётные числа. А два - вносят в список отдельно.

Можно оптимизировать ещё сильнее. Возьмём первые простые числа - например, 2,3,5; посчитаем их произведение = 30.
Запишем числа от 0 до 29=30-1. Выкинем все числа, которые делятся на начальный список - останется x =1,7,11,13,17,19,23,29; в этом списке есть 1, коотрое считается не-простое; и нет чисел из начального списка.
Запишем начальный список "2,3,5". Допишем к нему список "7,11,13,17,19,23,29" ("1" мы выкидываем).
Теперь мы ищем простые числа в виде "x+n*30", где n от 1 и далее. Среди тех которые мы отбросили - простых точно не будет.

Если проверять все числа подряд, то число проверок = 100%.
Если проверять только нечётные числа, то число проверок = 50%.
Если проверять в предложенном мной варианте, то число проверок = 8/30 = 26.7%, т.е. почти в четыре раза лучше, чем проверка всех чисел подряд (эффективность от сокращения перебора можно оценить как ln(30)=3.4).