Как определить в паскале что число простое
Алгоритмы нахождения простых чисел
Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.
(Единица не является простым числом!)
Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (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 и №3, но не всегда знают, как реализовать в программе досрочное завершение цикла, прием же №2 для них не очевиден, поэтому, возможно, учителю следует остановиться на нем более подробно или же привести полное доказательство этого утверждения.
Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.
Близнецы
Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.
Задача 3. Поиск пар чисел близнецов.
Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.
Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.
Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.
Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.
Задача 5. Приемы оптимизации алгоритма задачи 4.
Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.
Словесное описание алгоритма:
Эратосфеново решето
Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод.
Пусть написаны числа от 2 до n:
Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:
Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:
Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.
Задача 6. Нахождение простых чисел с помощью решета Эратосфена.
Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.
Словесное описание алгоритма:
Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)
Литература:
Как определить простое число
Подпишись на новости, чтобы ничего не пропустить
Условие задачи 2.30
Задача 2.30
Дан одномерный массив А, состоящий из натуральных чисел. Вывести на экран количество простых чисел в массиве.
Для начала напомню, что такое простые числа.
То есть если число делится без остатка только на 1 и на самого себя, то такое число является простым.
Например, простыми числами являются 2, 3, 5 и т.п.
А вот 4 уже не является простым, так как делится без остатка не только на 1 и 4, но ещё и на 2.
Если вы подзабыли, что такое натуральное число, то см. здесь.
Как определить простое число в Паскале
Алгоритм решения с подробным разбором приведу на Паскале. Решение на С++ можете посмотреть в примере программы на С++.
ВАЖНО!
На этом многие могут ошибиться. В определении сказано, что простое число имеет ровно два различных делителя. Следовательно, число 1 не является простым (также не является простым, так как ноль можно делить на любые числа).
Проверять, является ли число простым, будем с помощью функции, которую сами и создадим. Эта функция будет возвращать TRUE, если число простое.
В функции сначала будем проверять, не является ли число меньше двух. Если да, то это уже не простое число. Если же число равно 2 или 3, то оно является однозначно простым и делать какие-то дополнительные проверки не требуется.
А вот если число N будет больше трёх, то в этом случае в цикле будем перебирать все возможные делители, начиная от 2 до (N-1). Если на какой-то делитель число N делится без остатка, значит, это тоже не простое число. В этом случае мы прерываем цикл (потому что проверять дальше нет смысла), а функция возвращает FALSE.
Проверять, делится ли число на самоё себя нет смысла (поэтому цикл длится только до N-1).
Алгоритм нахождения простых чисел
Оптимизация алгоритма нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования 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
Определить простое число или нет
Нужно определить простое число или нет
Помогите кто может написать программу, которая могла бы определить простое число или нет (что бы.
Определить введенное число простое или составное
Определить введенное число простое или составное. Очень нужна. Можно на мыло jiehuh-das@ya.ru
Определить, кончается число на 7 или нет.
Вообщем вот задание, не понятен только 1 пункт, он отмечен жирным. Вводится последовательность.
Определить, введенное число кратно 3 или нет
Напишите программу, запрашиваемую число и дающее заключение введенное число кратно 3 или нет. И все.
Решение
Решение
Coffy, мало того, что НЕ максимально быстрая и лёгкая, так ещё и неверная. Пожалуйста, старайтесь проверять код перед тем, как выкладывать его на всеобщее обозрение.
Вычисление trunc(sqrt(a))) на каждой итерации скорости явно не добавляет, не находите? Лучше вычислить это значение один раз перед циклом.
Если в цикле было выяснено, что число составное, незачем проверять все числа до trunc(sqrt(a))), можно досрочно выйти из цикла.
Вот, почитайте тему: Алгоритм, который устанавливает – является ли число простым. Хотя, это тоже далеко не максимально простое и максимально лёгкое.
Определить, является ли натуральное число K степенью числа 3 или нет
Напишите пожалуйста программу по такому условию: Логической переменной присвоить TRUE или FALSE в.
Определить в тексте цифры и узнать число сост. из них симетрично или нет?
Задача такова: Программа должна определить есть ли в этом наборе символы соответсвующие десятичным.
Дано простое число. Составить функцию, которая находит следующее за ним простое число
Дано простое число. Составить функцию, которая находит следующее за ним простое число.
Дано простое число. Найти следующее за ним простое число
Дано простое число. Составить программу,которая будет находить следующее за ним простое.
Алгоритм, который устанавливает – является ли число простым
Является ли число простым
Определить является ли число простым. Состав те функцию определяющую простое число или нет.
Выяснить является ли число простым
Дано целое число N. Определить является ли оно простым. Как найти делители числа знаю,а вот что.
Определить, является ли число простым
While22. Дано целое число N (> 1). Если оно является простым, то есть не имеет положительных.
Определить, является ли заданное число простым
Паскаль. Определить,является ли заданное число простым. помогите пожалуйста написать.
Решение
Решение
Joy, по определению, число 1 простым не является.
Просто́е число́ — это натуральное число, большее единицы, имеющее ровно два натуральных делителя: 1 и само себя.
Для непростых значения не имеет, у них выход по Break будет всё равно не позже, а по простым будет меньше бегать, делители ведь парные, если до кв.корня не встретился делитель, то после его не будет уже гарантированно.
Добавлено через 1 минуту
Плюс, можно отдельно проверить на 2, а потом только на нечетные, вдвое сократит количество делений.
Добавлено через 2 минуты
А можно втихаря составлять табличку простых и проверять делимость только на них, будет еще быстрее. Но алгоритм выйдет несколько запутаннее.
Вот и вопрос: может, не нужен этот i mod 3. Лишний раз mod. Может, пусть себе это лишнее n mod i выполнится. Да, луше убрать, быстрее будет.
Добавлено через 14 минут
Хотя. При обработке массива чисел будут исключаться n 0
Читал когда-то давно. Ну, вероятностные алгоитмы для сравнительно малых чисел неэффективны, а для больших всё равно требуют дополнительной проверки на простоту числа, на то они и вероятностные. А решёта различные служат не для проверки простоты числа, а для нахождения всех простых чисел, меньших наперёд заданного числа. И не такие уж они простые, все эти Эратосфены и Аткины, всем им требуется немножко памяти. Ну да ладно. Вернёмся к нашим баранам.
У меня там тоже 2-4, только не столь эффективное, как У Вас. Я всё думал, как произвести инкремент числа то на 2, то на 4, исходя из самого i, ничего толкового не придумал, кроме того, что числа, которые требуется исключить, делятся на 3 нацело: 5, 7, 9, 11, 13, 15, 17, 19, 21, 23. и до Вашего варианта не дошёл, хотя, про xor мысль мелькала. Однако, вопрос об эффективности алгоритма с перебором делителей: фактически, 2-4 исключает из рассмотрения каждое третье нечётное число. Ну и, что имеем с гуся на каждые три числа?
Ну что, несколько поэффективней будет. Для ABC не подходит, но у меня он всё равно не стоит и я его ненавижу. Спасибо.
Формулу для описания простых чисел я знал ещё со школы, но как ею воспользоваться увидел только вчера
Спасибо!