Как узнать число простое. Как проверить, является ли число простым

Как проверить, является ли число простым. Как определить простое число

Числа бывают разными: натуральными, естественными, рациональными, целыми и дробными, положительными и отрицательными, комплексными и простыми, нечетными и четными, действительными и др. Из данной статьи можно узнать, что такое простые числа.

Какие числа называют английским словом “симпл”?

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

Составные числа

Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите – это в основном четные числа, но не все. А вот “двойка” – четное число и “первый номер” в ряду простых чисел.

Последовательность

Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть – делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных – только “два”. Сами десятки (10, 20. 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.

Теории о свойствах простых чисел

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

Простые числа — “строительные блоки” натуральных чисел

В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса – факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, “блоками” для построения натуральных чисел.

Поиск простых чисел. Тесты простоты

Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.

Имеет ли множество простых чисел предел?

О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).

Какое наибольшее простое число?

Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 2 31 – 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел – 2 57885161 – 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.

Названия специальных простых чисел

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

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

4. Биллхарта – Лемера – Селфриджа и др.

Современная наука не останавливается на достигнутом, и, вероятно, в ближайшем будущем мир узнает имена тех, кто смог получить приз в 250.000 долларов, найдя наибольшее простое число.

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

Простые и составные числа – определения и примеры

Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .

Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

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

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Составное число – это натуральное число, имеющее более двух положительных делителей.

Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а, то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.

Натуральные числа, которые не являются простыми, называют составными.

Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

Рассмотрим теорему, которая объясняет последнее утверждение.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.

Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Доказать что число 898989898989898989 является составным.

Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.

Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.

Определить составное или простое число 11723 .

Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

Ответ Ильи корректный, но не очень подробный. В 18 веке, кстати, единицу ещё считали простым числом. Например, такие крупные математики как Эйлер и Гольдбах. Гольдбах автор одной из семи задач тысячелетия – гипотезы Гольдбаха. В изначальной формулировке утверждается, что всякое чётное число представимо в виде суммы двух простых чисел. Причём изначально 1 учитывалась как простое число, и мы видим такое: 2 = 1+1. Это наименьший пример, удовлетворяющий исходной формулировке гипотезы. Позднее её подправили, и формулировка приобрела современный вид: “всякое чётное число, начиная с 4, представимо в виде суммы двух простых чисел”.

Вспомним определение. Простым является натуральное число р, имеющее только 2 различных натуральных делителя: само р и 1. Следствие из определения: у простого числа р только один простой делитель – само р.

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

1, равно как и 0, образуют другой класс чисел – класс нейтральных элементов относительно n-нарных операций в каком-то подмножестве алгебраического поля. При этом относительно операции сложения 1 является также образующим элементом для кольца целых чисел.

При таком рассмотрении не трудно обнаружить аналоги простых чисел в других алгебраических структурах. Предположим, что у нас есть мультипликативная группа, образованная из степеней 2, начиная с 1: 2, 4, 8, 16, . и т.д. 2 выступает здесь образующим элементом. Простым числом в этой группе назовём число, большее наименьшего элемента, и делящееся только на себя и на наименьший элемент. В нашей группе такими свойствами обладает только 4. Всё. Больше простых чисел в нашей группе не существует.

Если бы 2 тоже была простым числом в нашей группе, то см. первый абзац, – снова получилось бы, что простым числом является только 2.

Как проверить, является ли число простым. Как определить простое число

Числа бывают разными: натуральными, естественными, рациональными, целыми и дробными, положительными и отрицательными, комплексными и простыми, нечетными и четными, действительными и др. Из данной статьи можно узнать, что такое простые числа.

Какие числа называют английским словом “симпл”?

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

Составные числа

Противоположностью простых чисел являются составные. Они также являются натуральным, также больше единицы, но имеют не два, а большее количество делителей. Так, например, числа 4, 6, 8, 9 и т. д. являются натуральными, составными, но не простыми числами. Как видите – это в основном четные числа, но не все. А вот “двойка” – четное число и “первый номер” в ряду простых чисел.

Последовательность

Чтобы построить ряд простых чисел, необходимо совершить отбор из всех натуральных чисел с учетом их определения, то есть нужно действовать методом от противного. Необходимо рассмотреть каждое из натуральных положительных чисел на предмет того, имеет ли оно более двух делителей. Давайте постараемся построить ряд (последовательность), который составляют простые числа. Список начинается с двух, следующим идет три, поскольку оно делится только на себя и на единицу. Рассмотрим число четыре. Имеет ли оно делители, кроме четырех и единицы? Да, это число 2. Значит, четыре не является простым числом. Пять также является простым (оно, кроме 1 и 5, ни на какое другое число не делится), а вот шесть – делится. И вообще, если проследить за всеми четными числами, то можно заметить, что кроме “двух”, ни одно из них не является простым. Отсюда сделаем вывод, что четные числа, кроме двух, не являются простыми. Еще одно открытие: все числа, делящиеся на три, кроме самой тройки, будь то четные или нечетные, также не являются простыми (6, 9, 12, 15, 18, 21, 24, 27 и т.д.). То же самое касается и чисел, которые делятся на пять и на семь. Все их множество также не является простым. Давайте подведем итоги. Итак, к простым однозначным числам относятся все нечетные числа, кроме единицы и девятки, а из четных – только “два”. Сами десятки (10, 20. 40 и др.) не являются простыми. Двузначные, трехзначные и т. д. простые числа можно определить, исходя из вышеизложенных принципов: если они не имеют других делителей, кроме их самих и единицы.

Теории о свойствах простых чисел

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

Простые числа — “строительные блоки” натуральных чисел

В арифметике есть теорема, которая называется основной. Согласно ей, любое натуральное число, кроме единицы, можно представить в виде произведения, множителями которого являются простые числа, причем порядок следования множителей единственен, этот означает, что и способ представления единственен. Он называется разложением натурального числа на простые множители. Есть и другое название этого процесса – факторизация чисел. Исходя из этого, простые числа можно назвать “строительным материалом”, “блоками” для построения натуральных чисел.

Поиск простых чисел. Тесты простоты

Множество ученых разных времен пытались найти какие-то принципы (системы) для нахождения списка простых чисел. Науке известны системы, которые называются решето Аткина, решето Сундартама, решето Эратосфена. Однако они не дают каких-то существенных результатов, и для нахождения простых чисел используется простая проверка. Также математиками были созданы алгоритмы. Их принято называть тестами простоты. Например, существует тест, разработанный Рабином и Миллером. Его используют криптографы. Также существует тест Каяла-Агравала- Саскены. Однако он, несмотря на достаточную точность, очень сложен в вычислении, что принижает его прикладное значение.

Имеет ли множество простых чисел предел?

О том, что множество простых является бесконечностью, писал в книге “Начала” древнегреческий ученый Евклид. Он говорил так: “Давайте на минуту представим, что простые числа имеют предел. Тогда давайте перемножим их друг с другом, а к произведению прибавим единицу. Число, полученное в результате этих простых действий, не может делиться ни на одно из ряда простых чисел, потому что в остатке всегда будет единица. А это значит, что существует какое-то другое число, которое еще не включено в список простых чисел. Следовательно, наше допущение не верно, и это множество не может иметь предела. Помимо доказательства Евклида, существует более современная формула, данная швейцарским математиком восемнадцатого века Леонардом Эйлером. Согласно ему, сумма, обратная сумме первых n чисел растет неограниченно с ростом числа n. А вот формула теоремы относительно распределения простых чисел: (n) растёт, как n/ln (n).

Какое наибольшее простое число?

Все тот же Леонард Эйлер смог найти самое большое для своего времени простое число. Это 2 31 – 1 = 2147483647. Однако к 2013 году было вычислено другое наиболее точное самое большое в списке простых чисел – 2 57885161 – 1. Его называют числом Мерсенна. Оно содержит около 17 миллионов десятичных цифр. Как видите, число, найденное ученым из восемнадцатого века, в несколько раз меньше этого. Так и должно было быть, ведь Эйлер вел данный подсчет вручную, нашему же современнику наверняка помогала вычислительная машина. Более того, это число было получено на факультете математики в одном из американских факультетов. Числа, названные в честь этого ученого, проходят через тест простоты Люка-Лемера. Однако наука не желает останавливаться на достигнутом. Фонд Электронных рубежей, который был основан в 1990 году в Соединенных Штатах Америки (EFF), назначил за нахождение больших простых чисел денежную награду. И если до 2013 года приз полагался тем ученным, которые найдут их из числа 1 и 10 миллионов десятичных чисел, то сегодня это цифра достигла от 100 миллионов до 1 миллиарда. Размер призов составляет от 150 до 250 тысяч долларов США.

Названия специальных простых чисел

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

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

4. Биллхарта – Лемера – Селфриджа и др.

Современная наука не останавливается на достигнутом, и, вероятно, в ближайшем будущем мир узнает имена тех, кто смог получить приз в 250.000 долларов, найдя наибольшее простое число.

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

Простые и составные числа – определения и примеры

Простые и составные числа относят к целым положительным. Они обязательно должны быть больше единицы. Делители также подразделяют на простые и составные. Чтобы понимать понятие составных чисел, необходимо предварительно изучить понятия делителей и кратных.

Простыми числами называют целые числа, которые больше единицы и имеют два положительных делителя, то есть себя и 1 .

Составными числами называют целые числа, которые больше единицы и имеют хотя бы три положительных делителя.

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

Простые числа – это натуральные числа, имеющие только два положительных делителя.

Составное число – это натуральное число, имеющее более двух положительных делителей.

Любое число, которое больше 1 является либо простым, либо составным. Из свойства делимости имеем, что 1 и число а всегда будут делителями для любого числа а, то есть оно будет делиться само на себя и на 1 . Дадим определение целых чисел.

Натуральные числа, которые не являются простыми, называют составными.

Простые числа: 2 , 3 , 11 , 17 , 131 , 523 . Они делятся только сами на себя и на 1 . Составные числа: 6 , 63 , 121 , 6697 . То есть число 6 можно разложить на 2 и 3 , а 63 на 1 , 3 , 7 , 9 , 21 , 63 , а 121 на 11 , 11 , то есть его делители будут 1 , 11 , 121 . Число 6697 разложится на 37 и 181 . Заметим, что понятия простых чисел и взаимно простых чисел – разные понятия.

Для того, чтобы было проще использовать простые числа, необходимо использовать таблицу:

Таблица для всех существующих натуральных чисел нереальна, так как их существует бесконечное множество. Когда числа достигают размеров 10000 или 1000000000 , тогда следует задуматься об использовании решета Эратосфена.

Рассмотрим теорему, которая объясняет последнее утверждение.

Наименьший положительный и отличный от 1 делитель натурального числа, большего единицы, является простым числом.

Возьмем, что а является натуральным числом, которое больше 1 , b является наименьшим отличным от единицы делителем для числа а. Следует доказать, что b является простым числом при помощи метода противного.

Допустим, что b – составное число. Отсюда имеем, что есть делитель для b , который отличен от 1 как и от b . Такой делитель обозначается как b 1 . Необходимо, чтобы условие 1 q , так как происходит нарушение условия. Обе части неравенства b ≤ q следует умножить на любое положительное число b , не равное 1 . Получаем, что b · b ≤ b · q , где b 2 ≤ a и b ≤ a .

Из доказанной теоремы видно, что вычеркивание чисел в таблице приводит к тому, что необходимо начинать с числа, которое равняется b 2 и удовлетворяет неравенству b 2 ≤ a . То есть, если вычеркнуть числа, кратные 2 , то процесс начинается с 4 , а кратных 3 – с 9 и так далее до 100 .

Составление такой таблицы при помощи теоремы Эратосфена говорит о том, что при вычеркивании всех составных чисел, останутся простые, которые не превосходят n . В примере, где n = 50 , у нас имеется, что n = 50 . Отсюда и получаем, что решето Эратосфена отсеивает все составные числа, которые по значению не больше значения корня из 50 . Поиск чисел производится при помощи вычеркивания.

Перед решением необходимо выяснять, является ли число простым или составным. Зачастую используются признаки делимости. Рассмотрим это на ниже приведенных примере.

Доказать что число 898989898989898989 является составным.

Сумма цифр заданного числа равняется 9 · 8 + 9 · 9 = 9 · 17 . Значит, число 9 · 17 делится на 9 , исходя из признака делимости на 9 . Отсюда следует, что оно составное.

Такие признаки не способны доказать простоту числа. Если нужна проверка, следует производить другие действия. Самый подходящий способ – это перебор чисел. В течение процесса можно найти простые и составные числа. То есть числа по значению не должны превосходить a . То есть число а необходимо разложить на простые множители. если это будет выполнено, тогда число а можно считать простым.

Определить составное или простое число 11723 .

Теперь необходимо найти все делители для числа 11723 . Необходимо оценить 11723 .

Ответ Ильи корректный, но не очень подробный. В 18 веке, кстати, единицу ещё считали простым числом. Например, такие крупные математики как Эйлер и Гольдбах. Гольдбах автор одной из семи задач тысячелетия – гипотезы Гольдбаха. В изначальной формулировке утверждается, что всякое чётное число представимо в виде суммы двух простых чисел. Причём изначально 1 учитывалась как простое число, и мы видим такое: 2 = 1+1. Это наименьший пример, удовлетворяющий исходной формулировке гипотезы. Позднее её подправили, и формулировка приобрела современный вид: “всякое чётное число, начиная с 4, представимо в виде суммы двух простых чисел”.

Вспомним определение. Простым является натуральное число р, имеющее только 2 различных натуральных делителя: само р и 1. Следствие из определения: у простого числа р только один простой делитель – само р.

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

1, равно как и 0, образуют другой класс чисел – класс нейтральных элементов относительно n-нарных операций в каком-то подмножестве алгебраического поля. При этом относительно операции сложения 1 является также образующим элементом для кольца целых чисел.

При таком рассмотрении не трудно обнаружить аналоги простых чисел в других алгебраических структурах. Предположим, что у нас есть мультипликативная группа, образованная из степеней 2, начиная с 1: 2, 4, 8, 16, . и т.д. 2 выступает здесь образующим элементом. Простым числом в этой группе назовём число, большее наименьшего элемента, и делящееся только на себя и на наименьший элемент. В нашей группе такими свойствами обладает только 4. Всё. Больше простых чисел в нашей группе не существует.

Если бы 2 тоже была простым числом в нашей группе, то см. первый абзац, – снова получилось бы, что простым числом является только 2.

Как я могу проверить, является ли число простым числом?

Сначала я предложу пользователю ввести любое число. Затем мой код проверит, является ли число, введенное пользователем, простым числом или нет.

Но вопрос в том, что я не могу получить результат для 2 и 3. И когда я произвольно ввожу любые числа, такие как 134245, система выдаст много предложений. И я не знаю почему?

Ценю любые добрые души, которые помогут мне подняться 🙂

7 Ответов

вы должны остановиться, как только num % x == 0 истинно (нет необходимости в дальнейшем тестировании) и напечатать “это простое число” только в том случае, если цикл завершен без чего-либо напечатанного ранее.

Число является простым, если оно делится только на 1 и itself . В псевдокоде следующим образом:

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

Вы можете поместить логику в функцию и вернуть True или False для простого числа. Тогда вы можете просто проверить результат работы функции в вашем операторе if .

Посмотрите на свой код вот так:

Тело цикла выполняется на каждой итерации. Это означает, что вы печатаете что-то на каждой итерации , то есть для каждого x , который вы проверяете, чтобы увидеть, является ли он фактором num , вы печатаете. Это не то, что вы должны делать; чтобы определить, является ли число простым, вы сначала проверяете все возможные факторы, а затем печатаете свой результат. Так что вы не должны ничего печатать до окончания цикла.

Но вопрос в том, что я не могу получить результат для 2 и 3.

Вы переходите от 2 к ceil(sqrt(n)) . Для 2 и 3 это пустой диапазон, поэтому никакой итерации не происходит. Либо это частный случай, либо перепишите код так, чтобы он предполагал, что n является простым и пытается опровергнуть его в цикле.

система выведет много предложений.

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

Вот две процедуры Python для вычисления простых чисел. (Подсказка: Google для сита Эратосфена):

Похожие вопросы:

Я написал следующий код, который должен проверить, является ли введенное число простым числом или нет, но есть проблема, которую я не смог решить: def main(): n = input(Please enter a number:).

У меня есть этот код, который проверяет, является ли число простым числом: public static bool isPrime(int num) < if (num == 1) return false; if (num == 2) return true; int newnum =.

Здравствуйте я создал эту программу, чтобы проверить, является ли число простым числом. Он работает, но почему-то говорит, что 999-это простое число. Где же моя ошибка? Было бы здорово, если бы.

Я пытаюсь проверить, является ли это число простым (путем деления его на все числа ниже n). Вот моя попытка : bool isPrime(int n, int d)< if (d == 1) return true; else< if (n % d == 0)< return.

Что является эффективным способом, чтобы проверить, если Int32 N является простым числом Мерсенна? Это моя попытка : По-видимому, этот код возвращает true для некоторых чисел, которые являются.

Я пытаюсь сделать приложение, которое проверяет, является ли число простым или нет. Кто-нибудь может помочь мне проверить номер? Мне нужен простой ответ, а не невероятно продвинутые алгоритмы. Я.

Мне нужно написать программу, которая рекурсивно проверяет, является ли число числом Фибоначчи; легко сделать эту же задачу итеративно; также легко найти n-е число Фибоначчи рекурсивно, но я застрял.

Цветной Количество: Число может быть разбито на различные части подпоследовательности. Предположим, что число 3245 можно разбить на такие части, как 3 2 4 5 32 24 45 324 245 . И это число является.

Я пытался решить проблему проекта Эйлера 35, и мне нужно сделать функцию, которая скажет мне, является ли целое число круговым простым числом. У меня есть стандартная функция isprime и функция.

Мне нужно проверить, является ли число абсолютным целым числом. Я, кажется, легко могу преобразовать число в absint abs( intval( $_POST[‘number’] ) ); , но не могу понять, как его проверить: //.

Источники:

http://duslyk.ru/stomach-cancer/kak-proverit-yavlyaetsya-li-chislo-prostym-kak-opredelit-prostoe.html
http://duslyk.ru/stomach-cancer/kak-proverit-yavlyaetsya-li-chislo-prostym-kak-opredelit-prostoe.html
http://coderoad.ru/7456519/%D0%9A%D0%B0%D0%BA-%D1%8F-%D0%BC%D0%BE%D0%B3%D1%83-%D0%BF%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B8%D1%82%D1%8C-%D1%8F%D0%B2%D0%BB%D1%8F%D0%B5%D1%82%D1%81%D1%8F-%D0%BB%D0%B8-%D1%87%D0%B8%D1%81%D0%BB%D0%BE-%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%8B%D0%BC-%D1%87%D0%B8%D1%81%D0%BB%D0%BE%D0%BC