Поиск

Упражнение по нахождению простых чисел

Какой же учебник по программированию обходится без подобного упражнения? В этом упражнении мы рассмотрим небольшую программу, которая находит и распечатывает простые числа. Как известно, простое число делится только на 1 и на само себя, например: число 2 — простое, 3 — простое, а 4 — составное (делится на 1, 4 и 2). Существует бесконечное множество простых чисел и их нахождение требует довольно большого количества вычислений.

Наберите в текстовом редакторе программу, приведенную в листинге 3.5, и сохраните ее под именем primes. He нумеруйте строки. Сделайте файл выполняемым, следуя инструкциям, приведенным в конце 1-го занятия.

После этого попытайтесь запустить программу, набрав в командной строке:

perl primes

Проведем анализ программы.

  • Строка 1. В этой строке указан путь к интерпретатору (измените его в соответствии с конфигурацией вашей системы) и ключ -w. Всегда включайте режим выдачи предупреждений!
  • Строка 3. Переменной $maxprimes присваивается максимальное количество целых чисел, которые нужно найти.
  • Строка 4. Переменная $ value будет содержать значение, проверяемое на принадлежность к простым числам.
  • Строка 5. В переменной $count хранится счетчик найденных простых чисел.
  • Строка 6. Цикл while выполняется до тех пор, пока не будет найдено достаточное количество простых чисел.
  • Строка 7. Значение переменной $value увеличивается так, ^чтобы начать проверку на принадлежность к простым числам с числа 2.
  • Строка 8. Переменная $composite используется в цикле for как флажок. Она обозначает, что на текущей итерации исследуемое число не является простым.
  • Строки 9—10. Два вложенных цикла for перебирают все возможные множители числа $value. Например, для числа 4 будут проверяться пары 2 и 2, 2 и 3, 3 и 2, 3 и 3.
  • Строки 11-14. Значения переменных $i и $j перемножаются. Если их произведение равно $value, для этой переменной устанавливается флаг $composite и программа выходит из обоих циклов.
  • Строки 17—20. После циклов проверяется значение флага $composite. Если это Ложь, проверенное число является простым. В рассматриваемых строках выводится соответствующее сообщение и увеличивается значение счетчика.
Приведенный здесь алгоритм нахождения простых чисел не является самым быстрым или эффективным и служит лишь для демонстрации использования циклов. В любой книге, посвященной численным методам, вы сможете найти гораздо лучший алгоритм.