Напишите программу на Паскале, чтобы определить, является ли число, введенное с клавиатуры, простым числом
Обновлено: 21.11.2024
Я пытаюсь найти следующее простое число после числа, которое вводит пользователь, и я должен сделать это в паскале. Я даже не знаю, с чего начать, кто-нибудь может мне помочь?
Нет известной формулы для обнаружения простых чисел, кроме как взять список известных и использовать его или проверить все возможности грубой силой.
Создайте массив простых чисел, меньших входного, и для каждого числа большего, чем входное, попробуйте разделить на каждый элемент массива простых чисел. Если вы можете найти хотя бы один простой множитель, двигайтесь дальше, останавливайтесь, пока не найдете целое число с нулевыми множителями. .
Это домашнее задание, но я новичок в паскале, я знаю, что вы можете написать "ЕСЛИ он что-то делает, ТО сделайте что-нибудь еще", но можете ли вы написать "ЕСЛИ он что-то НЕ делает, тогда сделайте что-нибудь другое" .< /p>
4 ответа 4
Вы должны объявить n-элементный массив логических значений (значения простых чисел истинны), где n – число, введенное пользователем и умноженное на два. Затем найдите все простые числа до n, используя алгоритм решета Эратосфена (удалите все составные числа, изменив их значения на false). После этого найти следующее простое число после введенного значения будет легко. Индексы истинных значений являются простыми числами.
Попробуйте написать свой собственный код, а затем отредактируйте свой вопрос, если он не работает.
если введенное число = 2, то следующее простое число будет нечетным числом, большим введенного числа и меньшим, чем в два раза, чем введенное число (постулат Бертрана).
Нет, мы не будем писать для вас код Pascal.
Первым шагом в решении этой проблемы является выяснение того, как сделать это вручную. Из википедии:
Простой, но медленный метод проверки простоты заданного числа n известен как пробное деление. Он состоит в проверке того, является ли n кратным любому целому числу от 2 до sqrt.
Поэтому, если вам дано 6, вы должны сначала проверить число 7, чтобы убедиться, что оно простое. Вы проверяете, является ли число 7 простым, разделив все целые числа от 2 до квадратного корня из 7 (2,645751311). Таким образом, вам нужно только проверить, делится ли 7 на 2. Если пользователь вводит 14, вы должны сначала проверить, делится ли 15 на любое из целых чисел от 2 до квадратного корня из 15 (3,872983346). Таким образом, вы должны проверить, делится ли 15 на 2 или 3.
Здесь задействованы две петли. Один из них многократно добавляет 1 к введенному числу, то есть если они вводят 10, вы проверяете 11 на простоту, затем 12, затем 13, затем 14, затем 15 и т. д. Другой цикл делит все целые числа между 2 и квадратный корень из текущего числа проверяется на простоту. Делим на 2, есть остаток? Делим на 3, есть остаток? Делим на 4, есть остаток? И так далее. Каждый раз, когда вы получаете деление без остатка, вы можете остановить этот цикл, так как вы знаете, что не нашли простое число, и вам нужно увеличить значение, пересчитать квадратный корень и снова начать деление.
Число называется простым, если оно делится только на себя и на единицу. Это означает, что простые числа имеют только два делителя: один и само себя.
Число называется составным, если оно имеет более двух делителей.
Здесь следует отметить, что 1 не является ни простым, ни составным числом.
Условия для того, чтобы число было простым:
Оно должно быть больше единицы.
У него не должно быть больше двух факторов.
Вот некоторые из первых простых чисел: .
Здесь, в этой программе, нам дано число, и наша задача состоит в том, чтобы проверить, является ли данное число простым или нет. Но прежде чем двигаться дальше, если вы не знакомы с концепцией циклов в C, прочтите статью о циклах в C.
Ввод: введите число: 13
Вывод: это простое число
Эта проблема может быть решена следующими способами:
Способ 1. Использование цикла For
Способ 2. Использование функций
Способ 3. Использование sqrt(N)
Способ 4. Использование рекурсивной функции
Давайте рассмотрим каждый из этих методов отдельно.
Программа 1. Проверка, является ли число простым или нет
В этом методе мы напрямую проверяем, является ли число простым или нет, в самой основной функции, используя цикл for.
Алгоритм:
Объявить переменную
Инициализируйте переменную.
Используйте цикл for, который повторяется от 2 до N
Объявите количество и инициализируйте его равным 0.
Если число делится на любое из чисел между циклом, увеличивайте счетчик.
Если число не равно 0, это не простое число.
Если счетчик равен 0, то это простое число.
Ниже приведен код того же самого.
Приведенная ниже программа проверяет, является ли число простым в самом основном методе.
Введите число
11
Простое число
Программа 2. Проверка, является ли число простым или нет
В этом методе мы используем функцию для проверки того, является ли число простым или нет.
Алгоритм:
Объявить переменную.
Инициализировать переменную
Вызвать функцию, чтобы проверить, является ли число простым
Используйте цикл for, который повторяется от 2 до N/2
Объявите количество и инициализируйте его равным 0.
Если число делится на любое из чисел между циклом, увеличивайте счетчик.
Если число не равно 0, это не простое число.
Если счетчик равен 0, то это простое число.
Ниже приведен код того же самого.
Приведенная ниже программа демонстрирует, как проверить, является ли число простым или нет, с помощью функции.
Введите число
87
Не простое число
Программа 3. Проверка, является ли число простым или нет
Причина выбора sqrt(N) заключается в том, что наименьший и наибольший множители не могут быть больше, чем sqrt(N). В тот момент, когда мы находим какой-либо фактор, мы останавливаем дальнейшее выполнение цикла.
Алгоритм:
Объявить число.
Использование цикла for для перехода от 2 к sqrt(n)
Объявите переменную счетчика и инициализируйте ее значением 0.
Если число делится на любое другое число, увеличиваем счетчик и выходим из цикла.
Если число не равно нулю, то это не простое число.
Если счетчик равен нулю, то это простое число.
Ниже приведен код того же самого.
В приведенной ниже программе после объявления массива мы перебираем все элементы от 2 до sqrt(N) и проверяем каждый элемент, делится ли он на N. Если такое число найдено, возвращается false. Если какое-либо число не удовлетворяет критериям, это означает, что оно является простым числом.
Введите число
76
Не простое число
Программа 4. Проверка, является ли число простым или нет
В этом методе мы используем рекурсивный метод, чтобы проверить, является ли число простым или нет.
Алгоритм:
Объявить переменную
Инициализировать переменную
Вызов рекурсивной функции
Эта функция выполняет итерацию от 2 до N/2.
Если число делится на любое число от 2 до N/2, возвращается 0.
Если flag==1, то это простое число.
Если flag!=1, то это не простое число.
Ниже приведен код того же самого.
Приведенная ниже программа демонстрирует, как проверить, является ли число простым или нет, с помощью рекурсивной функции.
Читайте также: