Функция простого числа паскаль

Функция простого числа паскаль

Задача

Вводятся целые числа до первого числа, которое меньше двух. Определить, сколько простых чисел было введено.

Решение

  • q — счетчик простых чисел;
  • n — очередное введенное число.

Алгоритм решения задачи:

Пока введенное число больше 1, проверять его на простоту по следующему алгоритму:

  1. Если число делится на любой делитель от 2 до половины от себя, то оно не простое.
  2. Если число так и не разделилось ни на один из перебранных делителей, то оно простое, следовательно, увеличиваем счетчик простых чисел.

Программа на языке Паскаль:

Комментарии

Кривое определение простоты

Вместо for i : = 2 to n div 2 лучше написать for i : = 2 to round ( sqrt ( n ) ) Конечно, программа выдаст результат и так. Но для n=101 проверит 50 чисел вместо 10.

И стоит выделить блок "поиск простого числа" . Либо в функцию, либо комментарием — ведь программу будут читать неспециалисты 🙂

Задача: найти все простые числа, не превышающие заданного. Ниже код. Не могли бы вы проверить нет ли там ошибки. Я не совсем уверен что он работает корректно. Буду благодарен.

4 ответа 4

Вот, посмотрите. Что-то вроде такого должно быть.

Иногда бывает гораздо проще код просто переписать. Тогда повысится его читабельность.

Зачем Вы используете цикл while когда здесь нужен for , я не понял. Ну и как правильно заметили, проверять делимость нужно не до самого числа, а до его квадратного корня.

Вы можете проверить свою программу на наличие ошибок в автоматизированной системе. Например, здесь. Правда, ввод/вывод программы понадобится адаптировать для тестирующей системы, но это просто.

Можно воспользоваться идеями Сундарама, суть которых проста и логична.

  1. Просеивать только нечётные числа. Т.е. элемент решета a[m] должен содержать число m и соответствовать числу 2m+1 .
  2. Исключить из массива все числа вида i+j+2ij, поскольку 2(i+j+2ij)+1 = (2i+1)(2j+1) .
    Этого достаточно, поскольку все составные нечётные числа являются произведением нечётных чисел.
  3. Границы по меньшему индексу i определяются условием (2i+1) 2 ∈ [3, 2M+1], где M — размерность массива a .
    Т.е. i ∈ [1, sqrt(2M+1) / 2 -1 ]
  4. Границы по большему индексу j определяются условием i+j+2ij ∈ [1, M].
    Т.е. j ∈ [1, (M-i) / (2i+1)].
  5. Перебор по i и j проводится с шагом 1.
  6. Значения m , полученные в результате отбора, следует пересчитать в простые числа по формуле p=2m+1.

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

Читайте также:  1С не видит лицензию на сервере

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

Во все времена люди хотели найти как можно большее простое число. Пока люди считали только при помощи карандаша и бумаги, им нечасто удавалось обнаружить новые простые числа. До 1952 г. самое большое известное простое число состояло из 39 цифр. Теперь поиском все больших простых чисел занимаются компьютеры. Это может представлять интерес для любителей рекордов.

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

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, — простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

  1. рассматривать только нечетные числа;
  2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
  3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.
Читайте также:  Почему компьютер не видит фото с телефона

Как правило, учащиеся сами догадываются о приемах №1 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

  1. Вводим правую границу диапазона – m;
  2. Записываем двойку и тройку в файл;
  3. Пока очередное нечетное число i m ), вывести в файл количество простых чисел.
Читайте также:  Блокнот для редактирования html

Эратосфеново решето

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод.

Пусть написаны числа от 2 до n:

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

  1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
  2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
  3. Затем циклически повторим действия:
  1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
  2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

Литература:

  1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
  2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. — 255 с.
  3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. — 616 с.
Ссылка на основную публикацию
Adblock detector