Как проверить что число натуральное в c
Как проверить является ли число простым
Проверить, является ли число простым
3. Проверить, является ли число простым. Ввести с клавиатуры
Проверить, является ли заданное число простым
Дано целое число N (N>1). Проверить, является ли заданное число простым (простым называется число.
Проверить является ли заданное число простым
Не знаю как написать программу. Только начал учить С++ и задали задачу: написать программу которая.
Решение
Нет, я, конечно, получу много башмаков по башке за эту ссылку, но не могу её не запостить сюда, хотя бы ради общего развития.
Так же, для общего развития следует знать про это.
P.S. Здесь приведена реализация, правда только на Pacal (с ассеблером).
http://ru.wikipedia.org/wiki/%. 0%BD%D0%B0
ffantass, пользуйтесь википедией. вам предложен тупой перебор, хотя я даже не разбирался, что там напысано.
Либо выше алгоритм классный. Он вообще полиномиальный. И раз кнопки нет, хочется просто сказать спасибо AnyOne697 за интересные алгоритмы.
AnyOne697, алгоритмы хорошие и известные, никто не спорит, просто они вероятностные. Если целью является проверить относительно небольшое целое число, то лучше использовать детерминированный алгоритм.
Добавлено через 5 минут
ну да, для простого числа, состоящего из 8-10 десятичных цифр алгоритм придется как нельзя кстати
Добавлено через 1 минуту
polyaKIDze, всегда пожалуйста
ну да, так и есть. посмотрел первую и третью ваши ссылки, вот и упустил, спасибо). вы бы хоть назвали по-человечески эти ссылки, было бы понятнее, а то тыкаться в каждую ссылку под названием «ссылка» не каждый будет. поэтому я, в свою очередь, советую вам называть ссылки со смыслом, если их несколько.
P.S. Интересно, если AKS такой неплохой алгоритм, что же он не распространен.
ну да, так и есть. посмотрел первую и третью ваши ссылки, вот и упустил, спасибо). вы бы хоть назвали по-человечески эти ссылки, было бы понятнее, а то тыкаться в каждую ссылку под названием «ссылка» не каждый будет. поэтому я, в свою очередь, советую вам называть ссылки со смыслом, если их несколько.
P.S. Интересно, если AKS такой неплохой алгоритм, что же он не распространен.
Программирование на C, C# и Java
Уроки программирования, алгоритмы, статьи, исходники, примеры программ и полезные советы
ОСТОРОЖНО МОШЕННИКИ! В последнее время в социальных сетях участились случаи предложения помощи в написании программ от лиц, прикрывающихся сайтом vscode.ru. Мы никогда не пишем первыми и не размещаем никакие материалы в посторонних группах ВК. Для связи с нами используйте исключительно эти контакты: vscoderu@yandex.ru, https://vk.com/vscode
Является ли число простым – Проверяем на языке Си
Напишем на языке Си программу, проверяющую является ли число простым. Для проверки будем использовать простейший алгоритм, основанный непосредственно на определении простого числа.
Простое число – определение
Простое число – это натуральное число (то есть целое и положительное), большее, чем единица, которое делится без остатка только на единицу и само на себя.
Список простых чисел (приведем до ста) начинается так: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…
Функция на Си, проверяющая – является ли число простым
Напишем на языке Си функцию, которая будет проверять – простое ли число. И возвращать результат проверки в виде логической величины bool: true (да) или false (нет).
Алгоритм проверки числа n на простоту строится на определении термина простого числа.
Во-первых число n должно быть больше 1 (проверяем это в строке 5 с помощью условного оператора if), а во-вторых проверяемое число должно иметь только два делителя: 1 и n (проверяем это в строках 8-10 с помощью цикла for и оператора if).
Для работы данного метода требуется подключить заголовочный файл stdbool.h в начале файла с исходным кодом. В stdbool.h содержится определение логических констант true и false, поскольку в чистой версии языка Си они отсутствуют.
Для подключения используем директиву include:
Алгоритм проверки на простоту за O (log N)
Проверка на простоту
Чтобы определить, является ли данное число N простым, безусловно, достаточно написать простой цикл поиска делителей числа N:
Данная функция проверки числа на простоту достаточно эффективна — асимптотика ее работы O (sqrt(N)). Однако, иногда в спортивном программировании нужно уметь проверять число на простоту быстрее.
В некоторых случаях, когда требуется выполнять такую проверку для чисел из некоторого диапазона, то целесообразно воспользоваться алгоритмом Решето Эратосфена.
В данной статье я рассмотрю другой способ выполнять единичные проверки на простоту — тест Ферма.
Вероятностный алгоритм за O (log N) с тестом Ферма
Математическое обоснование теста Ферма достаточно хорошо описано здесь.
Я же приведу его конкретную реализацию на C++, а также покажу, как бороться с переполнением типа long long при возведении в степень.
Тест Ферма
Для того, чтобы проверить число N на простоту с достаточно хорошей вероятностью безошибочности, достаточно 100 раз проверить случайное число A тестом Ферма: 
Также стоит отметить, что числа A и N должны быть взаимно просты. Если это условие не выполняется, то число N — заведомо непростое.
Отмечу, что данная функция проверки использует функции нахождения НОД, а также быстрого возведения в степень по модулю.
Нахождение НОД
Собственно, в нахождении НОДа двух чисел проблем меньше всего. Воспользуемся алгоритмом Евклида:
Быстрое возведение в степень по модулю
Быстрое возведение в степень (бинарное) известно довольно широко. Отмечу только, что при перемножении двух чисел типа long long может произойти переполнение типа еще до того, как мы возьмем результат по модулю. Поэтому используем функцию двоичного умножения двух чисел также по модулю. Ее смысл очень похож на быстрое возведение в степень.
Точно также как и при возведении в степень, если второй множитель четный, то можно разделить его на 2, и перейти к вычислению произведения чисел A и B/2. Иначе, нужно вычислить произведение чисел A и B — 1.
Быстрая проверка натурального числа на простоту
Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.
Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов
Проверка на простоту числа
как мне сделать так, чтобы узнать простое является число или составное, не через bool, а как-нибудь.
Проверка числа на простоту
Помогите написать программу которая проверяет простое число или нет.
Проверка числа на простоту
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES.
Leomana, Вы как девушка, может напишите более красивый алгоритм:)
P.S. В третьем алгоритме массивы не используются, так как они только тормозят процесс, именно поэтому не стал рассматривать случаи 2*3*5*.
Добавлено через 8 минут
UFO94, вариант хороший и понятный использовать в совокупности решето Этатосфена с проверкой на простоту, но вопрос в память, действительно, упирается. Но, как вариант, попробуйте для сравнения 
Leomana, Вы как девушка, может напишите более красивый алгоритм:)
P.S. В третьем алгоритме массивы не используются, так как они только тормозят процесс, именно поэтому не стал рассматривать случаи 2*3*5*.
куда уж краше 
хм.. надо запомнить такую печальную вещь о массиве))
Мне вот еще интересно.. где же может появится необходимость узнать простое ли число?
вы о взломе шифров. нет, все это не подойдет, так как в реальных шифрах числа ОЧЕНЬ большие и все известные методы взлома шифров с открытым ключом имеют эспоненциальную сложность. тем более, в серьезных шифрах с открытым ключом и цифровых подписях используются эллиптические кривые, а там другие методы шифрования. так что мне просто интересны детерминированные алгоритмы проверки на простоту, не более. Тем более они меня сегодня заинтересовали, завтра другое заинтересует, наверное.
вы, наверное, RSA имеете ввиду. Там задача о факторизации, немного другое, нежели эта тема.
А кардинально «новое» это эллиптические кривые, они дают очень хороший эффект и используются очень успешно. Правда в RSA они эффекта не дают. Поэтому до сих пор RSA зависит от сложности задачи факторизации
для того чтобы пометить в массиве нужен цикл
для каждого числа свой(2,3,5. )
т.е выбрасывая итерации из проверки мы добавляем служебный цикл
, про шифрование я уже писал, что там очень большие числа, поэтому эти алгоритмы не применимы там. Просто интересно написать быстрый детерминированный алгоритм для чисел, умещающихся в стандартные типы данных.
ValeryS, немного не то. если числа принадлежат некоторому диапазону (от 1 до R), то решето Эратосфена достаточно построить до корня из R, об этом речь, если для R памяти нет, а для корня из R есть. А иначе алгоритм проверки получится банальным.
При этом никаких лишних циклов не надо, решето Эратосфена до корня из R строится заранее
Добавлено через 7 часов 58 минут
Интересно, но если модуль увеличить, скажем m = 2*3*5*7*11 = 2310, то из множества убираются из рассмотрения элементов и алгоритм обещает быть быстрее, но есть одно НО. Взаимно простых чисел с модулем m (меньших m) будет 480, которые каждый раз надо на m увеличивать. Это требует использования массива. И такой алгоритм работает медленнее чем три приведенных выше. Поэтому пока третий алгоритм получился самым быстрым. Так что в сторону увеличения модуля (что гарантировало бы использования дополнительной памяти фиксированного размера независимо от тестируемых чисел, что есть хорошо) нет смысла идти.
Алгоритмы поиска простых чисел в C#
Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.
Задача №1
Проверить является ли число простым и вывести результат вычисления в консоль.
Алгоритм определения простого числа
Для того, чтобы проверить является ли число N простым необходимо:
Реализация алгоритма определения простого числа в C#
Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:
Пример определения простых чисел из диапазона от 1 до N
Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.
Пример определения заданного количества простых чисел
Задача поиска простых чисел может быть сформулирована и по другому, например, так: найти первые N простых чисел. В этом случае нам будет выгодно использовать цикл while:
Результатом работы программы будет вывод в консоль первых N простых чисел.
Итого
Сегодня мы рассмотрели алгоритм поиска простых чисел и реализовали этот алгоритм в C#. В зависимости от условий задачи, мы использовали различные виды циклов для поиска набора простых чисел.