Нахождение простых чисел на PHP

Давайте напишем код, который будет проверять число на то, простое оно или нет. Простое число - это число, которое не делится ни на одно другое число (кроме как на 1 и на само себя - на это делятся все числа).

Самый простой способ проверить число на простоту - перебрать в цикле все числа от 2 до самого числа и в процессе перебора проверять, делится ли наше число хотя бы на одно из перебираемых чисел. Если ни на одно из этих чисел наше число не поделится - оно простое, а если хотя бы на одно поделится - оно составное.

Решим задачу через флаг.

Давайте установим начальное значение флага в true, считая число по умолчанию простым:

<?php $num = 31; // некоторое число $flag = true; // начальное значение флага ?>

Затем запустим цикл от 2 до нашего числа (не включая его), и в цикле будем проверять, делится ли наше число на счетчик цикла:

<?php $num = 31; $flag = true; for ($i = 2; $i < $num; $i++) { if ($num % $i === 0) { } } ?>

Очевидно, что если $num хотя бы один раз поделится на $i, то число не простое. В таком случае мы должны установить значение флага в false:

<?php $num = 31; $flag = true; for ($i = 2; $i < $num; $i++) { if ($num % $i === 0) { $flag = false; // если хотя бы один раз поделилось } } var_dump($flag); // выведем значение флага ?>

В общем-то задача решена. Есть, однако, один нюанс: даже если в какой-то итерации цикла мы определим, что число не простое, цикл все равно будет крутится до самого конца. Это не оптимально. Для решения проблемы добавим инструкцию break, осуществляющую выход из цикла, если число не простое:

<?php $num = 31; $flag = true; for ($i = 2; $i < $num; $i++) { if ($num % $i === 0) { $flag = false; break; // выйдем из цикла } } var_dump($flag); ?>

Самостоятельно, не подсматривая в мой код, повторите решение описанной задачи.