Меню

Как вывести все простые числа паскаль

Алгоритм нахождения простых чисел

Оптимизация алгоритма нахождения простых чисел

2 3 5 7 11 13 17 19 23 29 31… $250.000…

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

Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.

Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.

Очень быстро понимаешь, что в подсчете делителей каждого числа нет никакой надобности и поэтому переменную k можно освободить от своих обязанностей. Действительно, если хотябы один делитель имеется, то число уже не простое. Смотрим Листинг 2.

Конструкция break позволяет нам завершить выполнение внутреннего цикла и перейти к следующей итерации внешнего.
Далее возникает вопрос: «а зачем делить на 4, если на 2 число не делится?». Приходим к выводу, что искать делители нужно только среди простых чисел не превышающих делимое. Наш алгоритм превращается в… см. Листинг 3.

А потом вспоминаем теорию чисел и понимаем, что переберать надо только числа, не превосходящие корня из искомого. К примеру, если число M имеет делитель pi, то имеется делитель qi, такой, что pi * qi = M. То есть, чтобы найти пару, достаточно найти меньшее. Среди всех пар, предполагаемая пара с максимальным наименьшим — это пара с равными pi и qi, то есть pi * pi = M => pi = sqrt(M). Смотрим Листинг 4.

Код из Листинга 4 при N=10000 выполняется примерно в 1000 раз быстрее, чем самый первый вариант. Есть еще один «ускоритель», проверять только те числа, которые заканчиваются на 1, 3, 7 или 9 (так как остальные очевидно делятся на 2 или 5). Наблюдаем Листинг 5.

В следствии незначительного изменения Листинга 5 получаем небольшую прибавку в скорости:

Итого: Программа из последнего листинга выполняется, примерно, в 1300 раз быстрее первоначального варианта.
Я не ставил перед собой задачи написать программу максимально быстро решающую данную задачу, это скорее демонстрация начинающим программистам того, что правильно составленный алгоритм играет далеко не последнюю роль в оптимизации Ваших программ.

P.S.
Благодаря замечаниям получаем Листинг 7:

при N=10000, поучаем время:
time 1 = 26.24
time 2 = 3.113
time 3 = 0.413
time 4 = 0.096
time 5 = 0.087
time 6 = 0.083
time 7 = 0.053

Результаты при n = 1 000 000:
time 7 = 7.088
time 8 = 1.143

Источник

Алгоритмы нахождения простых чисел

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

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

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

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (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 ), вывести в файл количество простых чисел.
Читайте также:  Чем чистят каминные стекла

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

Греческий математик Эратосфен (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 с.

Источник

Найти все простые числа от 1 до N

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Найти все трехзначные простые числа. Определить функцию, позволяющую распознавать простые числа
помогите пожалуйста с программой Найти все трехзначные простые числа. Определить функцию.

Найти и напечатать все простые делители заданного натурального числа числа
1)найти и напечатать все простые делители заданного натурального числа числа

Найти все трехзначные числа,определив функцию, позволяющую распознавать простые числа
1)Найти все трехзначные числа,определив функцию, позволяющую распозновать простые числа. .

Найти все простые числа , не превышающие заданного числа
Задача: Найти все простые числа , не превышающие заданного числа w Мой вариант: .

Найти все простые числа, которые меньше числа N
Помогите, пожалуйста. Надо найти все простые числа, которые меньше данного числа N. Вычисление.

Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции
Найти все простые числа, меньше данного числа N. Определение простого числа описать в функции

Найти все трехзначные простые числа. Предусмотреть наличие подпрограммы для распознавания простого числа
Найти все трехзначные простые числа. Предусмотреть наличие подпрограммы для распознавания простого.

Перебором делителей найти простые числа в указанном диапазоне, и вывести все простые числа в поле Memo
Мне нужна программка на Delphi, которая простым перебором делителей находит простые числа в.

Читайте также:  Чем отмыть перманентный маркер со стекла

Источник

Вывести на экран все простые числа до заданного

Формулировка. Дано натуральное число. Вывести на экран все простые числа до заданного включительно.

Решение. В решении данной задачи используется решение предыдущей.

Нам необходимо произвести тест простоты числа, который был описан в решении предыдущей задачи следующим кодом (обозначим его как код 1):

for i := 1 to n do begin

if n mod i = 0 then inc(count)

Здесь n – проверяемое на простоту число. Напомним, что данный фрагмент кода в цикле проверяет, делится ли n на каждое i в отрезке от 1 до самого n, и если n делится на i, то увеличивает счетчик count на 1. Когда цикл заканчивается, на экран выводится результат проверки равенства счетчика числу 2.

В нашем же случае нужно провести проверку на простоту всех натуральных чисел от 1 до заданного числа (обозначим его как n). Следовательно, мы должны поместить код 1 в цикл по всем k от 1 до n. Также в связи с этим необходимо заменить в коде 1 идентификатор n на k, так как в данном решении проверяются на простоту все числа k. Кроме того, теперь вместо вывода ответа о подтверждении/опровержении простоты k необходимо вывести само это число в случае простоты:

if count = 2 then write(k, ‘ ‘);

Обобщая вышесказанное, приведем алгоритм на естественном языке:

1) Ввод n;

2) Запуск цикла, при котором k изменяется от 1 до n. В цикле:

  1. Обнуление переменной count;
  2. Запуск цикла, при котором i изменяется от 1 до k. В цикле:
  3. Если k делится на i, то увеличиваем значение переменной count на 1;
  4. Если count = 2, выводим на экран число k и символ пробела.

Код:

  1. program PrimesToN;
  2. var
  3. i, k, n, count: word;
  4. begin
  5. readln(n);
  6. for k := 1 to n do begin
  7. count := 0;
  8. for i := 1 to k do begin
  9. if k mod i = 0 then inc(count)
  10. end;
  11. if count = 2 then write(k, ‘ ‘)
  12. end
  13. end.

Вычислительная сложность. В данной задаче мы впервые столкнулись с вложенным циклом (когда один цикл запускается внутри другого). Это означает, что наш алгоритм имеет нелинейную сложность (при которой количество выполненных операций равно размерности исходных данных (в нашем случае это n – количество чисел) плюс некоторое количество обязательных операторов).

Давайте посчитаем количество выполненных операций в частном случае. Итак, пусть необходимо вывести все натуральные простые числа до числа 5. Очевидно, что проверка числа 1 пройдет в 1 + 2 шага, числа 2 – в 2 + 2 шага, числа 3 – в 3 + 2 шага и т. д. (прибавленная двойка к каждому числу – два обязательных оператора вне внутреннего цикла), так как мы проверяем делители во всем отрезке от 1 до проверяемого числа. В итоге количество проведенных операций (выполненных операторов на низшем уровне) представляет собой сумму: 3 + 4 + 5 + 6 + 7 (также опущен обязательный оператор ввода вне главного (внешнего) цикла). Очевидно, что при выводе всех простых чисел от 1 до n приведенная ранее сумма будет такой:

1 + 3 + 5 + 6 + … + (n – 1) + n + (n + 1) + (n + 2),

где вместо многоточия нужно дописать все недостающие члены суммы. Очевидно, что это сумма первых (n + 2) членов арифметической прогрессии с вычтенным из нее числом 2.

Как известно, сумма k первых членов арифметической прогрессии выражена формулой:

где a1 – первый член прогрессии, ak – последний.

Подставляя в эту формулу наши исходные данные и учитывая недостающее до полной суммы число 2, получаем следующее выражение:

Чтобы найти асимптотическую сложность алгоритма, отбросим коэффициенты при переменных и слагаемые с низшими степенями (оставив, соответственно, слагаемое с самой высокой степенью). При этом у нас остается член n 2 , значит, асимптотическая сложность алгоритма – O(n 2 ).

Конечно, в дальнейшем мы не будем так подробно находить асимптотическую сложность алгоритмов, а тем более, вычислять количество требуемых операций, что интересно только теоретически. На самом деле, конечно, нас интересует лишь порядок роста времени работы алгоритма (количества необходимых операций), который можно выявить из анализа вложенности циклов и некоторых других характеристик.

Источник