Числа которые ни на что не делятся

Числа которые ни на что не делятся

В предыдущей статье рассказывалось о числе Пи, сейчас мы поговорим о простых числах. Каждый знает, что простые числа — такие числа, которые делятся только на единицу и самих себя. Но так ли они просты, как кажутся, и актуальны ли сегодня? Попробуем разобраться.

История

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

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61 …

Доказательство того, что этих чисел бесконечно много, дал еще Евклид, живший в 300 г до н.э. Примерно в те же годы другой греческий математик, Эратосфен, придумал довольно-таки простой алгоритм получения простых чисел, суть которого была в последовательном вычеркивании чисел из таблицы. Те оставшиеся числа, которые ни на что не делились, и были простыми. Алгоритм называется «решето Эратосфена» и за счет своей простоты (в нем нет операций умножения или деления, только сложение) используется в компьютерной технике до сих пор.

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

Подчиняются ли простые числа каким-либо законам? Да, и они довольно любопытны.

Так, например, французский математик Мерсенн еще в 16 веке обнаружил, что много простых чисел имеет вид 2^N — 1, эти числа названы числами Мерсенна. Еще незадолго до этого, в 1588 году, итальянский математик Катальди обнаружил простое число 2 19 — 1 = 524287 (по классификации Мерсена оно называется M19). Сегодня это число кажется весьма коротким, однако даже сейчас с калькулятором проверка его простоты заняла бы не один день, а для 16 века это было действительно огромной работой.

На 200 лет позже математик Эйлер нашел другое простое число 2 31 — 1 = 2147483647. Опять же, необходимый объем вычислений каждый может представить сам. Он же выдвинул гипотезу (названную позже «проблемой Эйлера», или «бинарной проблемой Гольдбаха»), суть которой проста: каждое чётное число, большее двух, можно представить в виде суммы двух простых чисел.

Например, можно взять 2 любых четных числа: 123456 и 888777888.

С помощью компьютера можно найти их сумму в виде двух простых чисел: 123456 = 61813 + 61643 и 888777888 = 444388979 + 444388909. Интересно здесь то, что точное доказательство этой теоремы не найдено до сих пор, хотя с помощью компьютеров она была проверена до чисел с 18 нулями.

Существует и другая теорема математика Пьера Ферма, открытая в 1640 году, которая говорит о том, что если простое число имеет вид 4*k+1, то оно может быть представлено в виде суммы квадратов других чисел. Так, например, в нашем примере простое число 444388909 = 4*111097227 + 1. И действительно, с помощью компьютера можно найти, что 444388909 = 19197*19197 + 8710*8710.

Теорема была доказана Эйлером лишь через 100 лет.

И наконец Бернхардом Риманом в 1859 году была выдвинута так называемая «Гипотеза Римана» о количестве распределения простых чисел, не превосходящих некоторое число. Эта гипотеза не доказана до сих пор, она входит в список семи «проблем тысячелетия», за решение каждой из которых Математический институт Клэя в Кембридже готов выплатить награду в один миллион долларов США.

Так что с простыми числами не все так просто. Есть и удивительные факты. Например, в 1883 г. русский математик И.М. Первушин из Пермского уезда доказал простоту числа 2 61 — 1 = 2305843009213693951. Даже сейчас бытовые калькуляторы не могут работать со столь длинными числами, а на то время это была поистине гигантская работа, и как это было сделано, не очень ясно до сих пор. Хотя действительно существуют люди, обладающие уникальными способностями мозга — так например, известны аутисты, способные находить в уме (!) 8-значные простые числа. Как они это делают, непонятно.

Современность

Актуальны ли простые числа сегодня? Еще как! Простые числа являются основой современной криптографии, так что большинство людей пользуются ими каждый день, даже не задумываясь об этом. Любой процесс аутентификации, например, регистрация телефона в сети, банковские платежи и прочее, требуют криптографических алгоритмов.

Суть идеи тут крайне проста и лежит в основе алгоритма RSA, предложенного еще в 1975 году. Отправитель и получатель совместно выбирают так называемый «закрытый ключ», который хранится в надежном месте. Этот ключ представляет собой, как, наверное, читатели уже догадались, простое число. Вторая часть — «открытый ключ», тоже простое число, формируется отправителем и передается в виде произведения вместе с сообщением открытым текстом, его можно опубликовать даже в газете. Суть алгоритма в том, что не зная «закрытой части», получить исходный текст невозможно.

К примеру, если взять два простых числа 444388979 и 444388909, то «закрытым ключом» будет 444388979, а открыто будут передано произведение 197481533549433911 (444388979*444388909). Лишь зная вторую половинку, можно вычислить недостающее число и расшифровать им текст.

В чем тут хитрость? А в том, что произведение двух простых чисел вычислить несложно, а вот обратной операции не существует — если не знать первой части, то такая процедура может быть выполнена лишь перебором. И если взять действительно большие простые числа (например, в 2000 символов длиной), то декодирование их произведения займет несколько лет даже на современном компьютере (к тому времени сообщение станет давно неактуальным).

Гениальность данной схемы в том, что в самом алгоритме нет ничего секретного — он открыт и все данные лежат на поверхности (и алгоритм, и таблицы больших простых чисел известны). Сам шифр вместе с открытым ключом можно передавать как угодно, в любом открытом виде. Но не зная секретной части ключа, которую выбрал отправитель, зашифрованный текст мы не получим. Для примера можно сказать, что описание алгоритма RSA было напечатано в журнале в 1977 году, там же был приведен пример шифра. Лишь в 1993 году при помощи распределенных вычислений на компьютерах 600 добровольцев, был получен правильный ответ.

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

Все простые числа – нечётные, поэтому они никогда не идут друг за другом, то есть два простых числа всегда разделены, по крайней мере, одним числом, которое является чётным. Исключение составляют числа 2 и 3, так как 2 является единственным чётным простым числом.

Читайте также:  Сочетание клавиш объединение ячеек word

В первой сотне натуральных чисел мы можем найти следующие пары чисел, отделённых друг от друга одним числом:

(3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61) и (71, 73).

Такие простые числа называются «числами-близнецами» или «парными». Простые числа-близнецы по мере увеличения встречаются реже и реже. Но компьютерные вычисления показывают, что парные числа продолжают встречаться даже среди необыкновенно больших чисел. Самыми большими известными числами-близнецами (открытыми в 2016 г.) являются числа:

2 996 863 034 895 × 2 1290000 -1

2 996 863 034 895 × 2 1290000 +1

Поиск простых чисел всегда занимал умы великих математиков. Самый первый и самый простой метод приписывают древнегреческому математику Эратосфену (273–194 до н.э.). Метод называется «решето Эратосфена».

Эратосфен

Греческий математик, астроном, географ, филолог и поэт. Основатель научной хронологии, автор работ по измерению окружности Земли.

На примере чисел от 1 до 100 покажем, как при помощи этого метода «просеиваются» простые числа.

  1. Составим таблицу натуральных чисел от 1 до 100.
  2. Вычеркнем единицу и все числа, кратные двум: 4, 6, 8, 10…
  3. Вычеркнем все числа, кратные трём: 6 (уже вычеркнули), 9, 12, 15…
  4. Аналогично вычеркнем числа, кратные пяти, семи и т. д.

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

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

В первой тысяче натуральных чисел находится всего 168 простых чисел. Можно предположить, что в каждой следующей тысяче количество простых чисел не будет сильно изменяться. Но это далеко не так. Например, среди чисел в промежутке между числами 10 100 и 10 100 +1000 существует только два простых числа. Более того, существуют еще бóльшие пробелы, например, 20 000 идущих подряд чисел, среди которых нет ни одного простого числа. Как такое возможно?

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

Доказательство. Рассмотрим произведение первых пяти натуральных чисел:

1×2×3×4×5 =120

Примечание. Выражение 1x2x3x4x5 удобнее записать следующим образом — 5!, которое в математике называется «фaкториaл числа пять».Очевидно, что 5! это составное число.

Ясно также, что число 5! + 2 = 122 также не является простым. Оно делится на 2, так как оба слагаемых содержат множитель 2. Аналогично, число

5! + 3 =123

не является простым, оно делится на 3.

5! + 4 =124 и 5! + 5 =125

также не являются простыми,

так как делятся на 4 и 5 соответственно.

Итак, мы получили четыре последовательных числа — 122, 123, 124, 125, которые не являются простыми числами.

Аналогично можно составить ряд из ста (миллиона, триллиона) последовательных чисел, не содержащих простых чисел. А это значит, что по мере продвижения по ряду натуральных чисел, простые числа встречаются всё реже и реже.

Означает ли то, что простые числа встречаются всё реже и реже, то, что может наступить момент, когда простые числа больше не появятся? Нет, не означает. Античный математик Евклид очень элегантно и остроумно доказал, что множество простых чисел бесконечно.

Евклид

Древнегреческий математик известный как «отец геометрии». Автор трактата «Начало» — первого дошедшего до нас труда по математике.

Множество простых чисел бесконечно, и каким бы длинным не был ряд составных чисел, в конце концов появится простое число.

Доказательство. Предположим, что нам известны только следующие простые числа:

Перемножим их и добавим к результату единицу:

2×3×5 + 1 =31

Ясно, что число 31 не делится ни на одно простое число (2, 3, 5). А это означает, что мы нашли новое простое число.

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

Возьмём теперь следующий ряд простых чисел:

Перемножим их и добавим единицу:

2×3×5×7×11×13 + 1 = 30 031

Полученное число также не будет делиться ни на одно из исходных простых чисел. Но это ещё не значит, что оно простое.

Согласно «Основной теореме арифметики», которую сформулировал Евклид, «любое натуральное число может быть единственным образом разложено в произведение простых множителей».

Действительно, число 30 031 может быть разложено в произведение двух других простых чисел:

30 031 = 59 × 509

В этом случае мы также нашли два новых простых числа —

59 и 509

Каким бы ни был первоначальный ряд простых чисел, при их перемножении и добавлении единицы получится:

  1. либо новое простое число, которого нет в первоначальном ряду;
  2. либо составное число, при разложении которого на простые множители получаются новые простые числа, которых также нет в первоначальном ряду.

К сожалению, этот метод не позволяет найти все простые числа.

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

Навигация по странице.

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

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

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

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

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

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

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

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

Отметим, что каждое целое положительное число, большее единицы, есть либо простое, либо составное число. Иными словами, не существует ни одного такого целого числа, которое не являлось бы ни простым, ни составным. Это следует из свойства делимости, которое гласит, что числа 1 и a всегда являются делителями любого целого числа a .

Читайте также:  Программа от хакерских атак

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

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

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

Например, числа 2 , 3 , 11 , 17 , 131 , 523 являются простыми. Несомненно, это далеко не очевидно. Но все наши попытки подобрать какой-либо положительный делитель любого из этих чисел, отличный от единицы и самих этих чисел, закончатся неудачей. Это свидетельствует о том, что записанные числа являются простыми. В последнем пункте данной статьи мы более подробно поговорим о доказательстве простоты данного числа.

В качестве примеров составных чисел приведем 6 , 63 , 121 и 6 697 . Это утверждение тоже нуждается в пояснении. Число 6 имеет кроме положительных делителей 1 и 6 еще и делители 2 и 3 , так как 6=2·3 , поэтому 6 – действительно составное число. Положительными делителями 63 являются числа 1 , 3 , 7 , 9 , 21 и 63 . Число 121 равно произведению 11·11 , поэтому его положительными делителями являются 1 , 11 и 121 . А число 6 697 составное, так как его положительными делителями кроме 1 и 6 697 являются еще и числа 37 и 181 .

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

Таблица простых чисел

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

Возникает логичный вопрос: «Почему мы заполнили таблицу простых чисел только до 1 000 , разве нельзя составить таблицу всех существующих простых чисел»?

Ответим сначала на первую часть этого вопроса. Для большинства задач, при решении которых придется использовать простые числа, нам будет вполне достаточно простых чисел в пределах тысячи. В остальных случаях, скорее всего, придется прибегать к каким-либо специальным приемам решения. Хотя, несомненно, мы можем составить таблицу простых чисел до сколь угодно большого конечного целого положительного числа, будь то 10 000 или 1 000 000 000 , в следующем пункте мы поговорим о методах составления таблиц простых чисел, в частности, разберем способ, получивший название решето Эратосфена.

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

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

Пусть a – натуральное число, большее единицы, и b – наименьший положительный и отличный от единицы делитель числа a . Докажем, что b – простое число методом от противного.

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

Так как число a делится на b по условию, и мы сказали, что b делится на b1 , то понятие делимости позволяет говорить о существовании таких целых чисел q и q1 , что a=b·q и b=b1·q1 , откуда a= b1·(q1·q) . Из правил умножения целых чисел следует, что произведение двух целых чисел есть целое число, тогда равенство a=b1·(q1·q) указывает на то, что b1 является делителем числа a . Учитывая полученные выше неравенства 1 , мы получаем противоречие условию, что b – наименьший положительный и отличный от единицы делитель числа a .

Теперь мы можем доказать, что простых чисел бесконечно много.

Простых чисел бесконечно много.

Предположим, что это не так. То есть, предположим, что простых чисел всего n штук, и эти простые числа есть p1, p2, …, pn . Покажем, что мы всегда можем найти простое число, отличное от указанных.

Рассмотрим число, p равное p1·p2·…·pn+1 . Понятно, что это число отлично от каждого из простых чисел p1, p2, …, pn . Если число p — простое, то теорема доказана. Если же это число составное, то в силу предыдущей теоремы существует простой делитель этого числа (обозначим его pn+1 ). Покажем, что этот делитель не совпадает ни с одним из чисел p1, p2, …, pn .

Если бы это было не так, то по свойствам делимости произведение p1·p2·…·pn делилось бы на pn+1 . Но на pn+1 делится и число p , равное сумме p1·p2·…·pn+1 . Отсюда следует, что на pn+1 должно делиться второе слагаемое этой суммы, которое равно единице, а это невозможно.

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

Итак, в силу того, что простых чисел бесконечно много, при составлении таблиц простых чисел всегда ограничивают себя сверху каким-либо числом, обычно, 100 , 1 000 , 10 000 и т.д.

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

Сейчас мы обсудим способы составления таблиц простых чисел. Предположим, что нам нужно составить таблицу простых чисел до 100 .

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

Опишем несколько первых шагов.

Начинаем с числа 2 . Число 2 не имеет положительных делителей, кроме 1 и 2 . Следовательно, оно простое, поэтому, заносим его в таблицу простых чисел. Здесь следует сказать, что 2 является наименьшим простым числом. Переходим к числу 3 . Его возможным положительным делителем, отличным от 1 и 3 , является число 2 . Но 3 на 2 не делится, поэтому, 3 – простое число, и его также нужно занести в таблицу простых чисел. Переходим к числу 4 . Его положительными делителями, отличными от 1 и 4 , могут быть числа 2 и 3 , проверим их. Число 4 делится на 2 , поэтому, 4 – составное число, и его не нужно заносить в таблицу простых чисел. Обратим внимание на то, что 4 – наименьшее составное число. Переходим к числу 5 . Проверяем, являются ли его делителем хотя бы одно из чисел 2 , 3 , 4 . Так как 5 не делится ни на 2 , ни на 3 , ни на 4 , то оно простое, и его надо записать в таблицу простых чисел. Дальше происходит переход к числам 6 , 7 , и так далее до 100 .

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

Читайте также:  Процедуры в паскале abc

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

Покажем решето Эратосфена в действии при составлении таблицы простых чисел до 50 .

Сначала записываем по порядку числа 2, 3, 4, …, 50 .

Первое записанное число 2 является простым. Теперь от числа 2 последовательно перемещаемся вправо на два числа и зачеркиваем эти числа, пока не доберемся до конца составляемой таблицы чисел. Так будут вычеркнуты все числа, кратные двум.

Первым следующим за 2 невычеркнутым числом является 3 . Это число простое. Теперь от числа 3 последовательно перемещаемся вправо на три числа (учитывая и уже зачеркнутые числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные трем.

Первым следующим за 3 невычеркнутым числом является 5 . Это число простое. Теперь от числа 5 последовательно перемещаемся вправо на 5 чисел (учитываем и зачеркнутые ранее числа) и вычеркиваем их. Так будут вычеркнуты все числа, кратные пяти.

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

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

Наименьший положительный и отличный от единицы делитель составного числа a не превосходит , где — арифметический квадратный корень из a .

Обозначим буквой b наименьший и отличный от единицы делитель составного числа a (число b является простым, что следует из теоремы, доказанной в самом начале предыдущего пункта). Тогда существует такое целое число q , что a=b·q (здесь q – положительное целое число, что следует из правил умножения целых чисел), причем (при b>q нарушится условие, что b – наименьший делитель числа a , так как q также является делителем числа a в силу равенства a=q·b ). Умножив обе части неравенства на положительное и большее единицы целое число b (это нам позволяют сделать свойства числовых неравенств), получаем , откуда и .

Что же нам дает доказанная теорема, касательно решета Эратосфена?

Во-первых, вычеркивание составных чисел, кратных простому числу b следует начинать с числа, равного (это следует из неравенства ). Например, вычеркивание чисел, кратных двум, следует начинать с числа 4 , кратных трем – с числа 9 , кратных пяти – с числа 25 , и так далее.

Во-вторых, составление таблицы простых чисел до числа n с помощью решета Эратосфена можно считать законченным тогда, когда будут вычеркнуты все составные числа, кратные простым числам, не превосходящим . В нашем примере n=50 (так как мы составляем таблицу простых чисел до 50 ) и , поэтому решето Эратосфена должно отсеять все составные числа, кратные простым числам 2 , 3 , 5 и 7 , которые не превосходят арифметического квадратного корня из 50 . То есть, нам дальше не нужно заниматься поиском и вычеркиванием чисел, кратных простым числам 11 , 13 , 17 , 19 , 23 и так далее до 47 , так как они уже будут вычеркнуты, как кратные меньшим простым числам 2 , 3 , 5 и 7 .

Данное число простое или составное?

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

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

Докажите, что число 898 989 898 989 898 989 составное.

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

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

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

Число 11 723 простое или составное?

Выясним, до какого простого числа могут быть делители числа 11 723 . Для этого оценим .

Достаточно очевидно, что , так как 200 2 =40 000 , а 11 723 (при необходимости смотрите статью сравнение чисел). Таким образом, возможные простые делители числа 11 723 меньше числа 200 . Это уже значительно облегчает нашу задачу. Если бы мы этого не знали, то нам бы пришлось перебирать все простые числа не до 200 , а вплоть до числа 11 723 .

При желании можно оценить более точно. Так как 108 2 =11 664 , а 109 2 =11 881 , то 108 2 2 , следовательно, . Таким образом, любое из простых чисел, меньших 109 , потенциально является простым делителем данного числа 11 723 .

Теперь мы будем последовательно делить число 11 723 на простые числа 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 , 101 , 103 , 107 . Если число 11 723 разделится нацело на одно из записанных простых чисел, то оно будет составным. Если же оно не делится ни на одно из записанных простых чисел, то исходное число простое.

Не будем описывать весь этот монотонный и однообразный процесс деления. Сразу скажем, что 11 723 не делится нацело на простые числа 2 , 3 , 5 , 7 , 11 , 13 , 17 , а на 19 – делится. Вот тому подтверждение в виде деления столбиком:

Следовательно, число 11 723 – составное, так как кроме 1 и самого себя имеет делитель 19 .

Ссылка на основную публикацию
Хороший принтер для школьника
Для ученика возможность распечатывать доклады, рефераты и иллюстрации для занятий в школе - совсем не лишняя. Школьнику в XXI веке...
Файл с расширением dav чем открыть
Файл формата DAV открывается специальными программами. Чтобы открыть данный формат, скачайте одну из предложенных программ. Чем открыть файл в формате...
Файл подкачки windows 7 на флешку
В прошлой статье рассказано, как определиться с оптимальным размером файла подкачки, что делать с SSD-дисками и как установить размер файла...
Хороший телефон с aliexpress
Обновлено 22.10.2019 На Алиэкспресс есть много разных производителей смартфонов. Даже есть такие международные бренды, как Apple. В этой подборке мы...
Adblock detector