Перебор делителей. По определению число n является простым лишь в том случае, если оно не делится без остатка на 2 и другие целые числа, кроме 1 и самого себя. Приведенная выше формула позволяет удалить ненужные шаги и сэкономить время: например, после проверки того, делится ли число на 3, нет необходимости проверять, делится ли оно на 9.

• Функция floor(x) округляет число x до ближайшего целого числа, которое меньше или равно x.

Узнайте о модульной арифметике. Операция "x mod y" (mod является сокращением латинского слова "modulo", то есть “модуль”) означает "поделить x на y и найти остаток". Иными словами, в модульной арифметике по достижении определенной величины, которую называют модулем , числа вновь "превращаются" в ноль. Например, часы отсчитывают время с модулем 12: они показывают 10, 11 и 12 часов, а затем возвращаются к 1.

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

Узнайте о подводных камнях малой теоремы Ферма. Все числа, для которых не выполняются условия теста, являются составными, однако остальные числа лишь вероятно относятся к простым. Если вы хотите избежать неверных результатов, поищите n в списке "чисел Кармайкла" (составных чисел, которые удовлетворяют данному тесту) и "псевдопростых чисел Ферма" (эти числа соответствуют условиям теста лишь при некоторых значениях a ).

Если удобно, используйте тест Миллера-Рабина. Хотя данный метод довольно громоздок при вычислениях вручную, он часто используется в компьютерных программах. Он обеспечивает приемлемую скорость и дает меньше ошибок, чем метод Ферма. Составное число не будет принято за простое, если провести расчеты для более ¼ значений a . Если вы случайным способом выберете различные значения a и для всех них тест даст положительный результат, можно с достаточно высокой долей уверенности считать, что n является простым числом.

Для больших чисел используйте модульную арифметику. Если у вас под рукой нет калькулятора с функцией mod или калькулятор не рассчитан на операции с такими большими числами, используйте свойства степеней и модульную арифметику, чтобы облегчить вычисления. Ниже приведен пример для 3 50 {\displaystyle 3^{50}} mod 50:

• Перепишите выражение в более удобном виде: mod 50. При расчетах вручную могут понадобиться дальнейшие упрощения.
• (3 25 ∗ 3 25) {\displaystyle (3^{25}*3^{25})} mod 50 = mod 50 mod 50) mod 50. Здесь мы учли свойство модульного умножения.
• 3 25 {\displaystyle 3^{25}} mod 50 = 43.
• (3 25 {\displaystyle (3^{25}} mod 50 ∗ 3 25 {\displaystyle *3^{25}} mod 50) mod 50 = (43 ∗ 43) {\displaystyle (43*43)} mod 50.
• = 1849 {\displaystyle =1849} mod 50.
• = 49 {\displaystyle =49} .

Думаю, что может. это сумма чисел 2 и 3. 2+3=5. 5 то же простое число. Оно делиться на себя и 1.

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

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

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

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

Конечно, ответ на этот вопрос был бы отрицательным, если бы не вездесущая двойка, которая как оказывается, тоже является простым числом.А ведь она подпадает под правило простых чисел:делится на 1 и на само себя.И вот из-за не и ответ на вопрос становится положительным.Множество простых чисел и двойки дат тоже простое число.Иначе бы все остальные в сумме давали бы число чтное, что является (кроме 2) числами не простыми.О так с 2- получаем целый ряд тоже простых чисел.

Начиная с 2+3=5.

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

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



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

2+17=19 и т.д.

Как мы видим все простые числа нечетные, а для получения в сумме нечетного числа слагаемые должны быть четное + нечетное. Получается, что для получения в сумме двух простых чисел простого числа надо прибавить простое число к 2.

Для начала нужно вспомнить, что простые числа это такие числа, которые могут делиться только на единицу и на саму себя без остатка. Если число имеет кроме этих двух делителей еще и другие делители, которые не оставляют остатка, то это уже не простое число. Цифра 2 тоже простое число. Сумма двух простых чисел конечно же может быть простым числом. Взять даже 2 + 3 будет 5 - простое число.

Перед тем, как на такой вопрос ответить, нужно подумать, а не сходу отвечать. Так как многие забывают о том, что есть одно чтное число, при это оно является простым. Это число 2. И благодаря ему ответ на вопрос автора: да!, такое вполне возможно, причм примеров такого довольно много. К примеру 2+3=5, 311+2=313.



К простым числам относятся те, которые делятся на себя и на единицу.



прилагаю таблицу с простыми числами до числа 997

все эти числа делятся только на два числа - на себя и на единицу, третьего делителя нет.

к примеру число 9 уже не простое, так как имеет еще делители помимо 1 и 9, это - 3

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

Из школьного курса математики мы знаем. что сумма двух простых чисел также может быть простым числом. Например 5+2=7 и т.п. Простым же называется то число, которое может делиться на само себя или же ни цифру один. То есть таких чисел довольно много и всоей сумме они также могут давать простое число.

Да, может. Если чтко знать, что именно представляет собой простое число, то это достаточно легко можно определить. Количество делителей простого числа строго ограничено - это только единица и само это число, т.е., чтобы ответить на этот вопрос, достаточно будет взглянуть на таблицу простых чисел - судя по всему, одним из слагаемых в данной сумме обязательно должно быть число 2. Пример: 41 + 2 = 43.

Для начала вспомним, что такое простое число - это такое число, которое можно поделить на такое же и на единицу. А теперь отвечаем на вопрос - да, может. Но только в одном случае, когда одно слагаемое -любое простое число, а другое слагаемое - 2.

Если учесть то, что простое число-которое можно поделить на само себя, на такое же и на 1.

То-да, может.Простой пример 2+3=5 или 2+5=7

и 5 и 7 делятся на самих себя, и на 1.

Все очень просто, если вспомнить школьные годы.

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

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 добровольцев, был получен правильный ответ.

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

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

Какие числа являются простыми

Как же определить простое число? Многие числа делятся без остатка на другие числа. Число, на которое делится целое число, мы называем делителем.

В данном случае мы говорим о делении без остатка. Например, число 36 можно разделить на 1, 2, 3, 4, 6, 9, 12, 18 и на само себя, то есть на 36. Значит, 36 имеет 9 делителей. Число 23 делится только на себя и на 1, то есть это число имеет 2 делителя – это число является простым.

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

Для математиков открытие закономерностей в ряду чисел, которые потом можно использовать для построения гипотез, является очень приятным событием. Но простые числа отказываются подчиняться хоть какой-нибудь закономерности. Но есть способ определения простых чисел. Этот способ найден Эратосфеном, он называется «решетом Эратосфена». Давайте рассмотрим вариант такого «решета», представленный в виде таблицы чисел до 48 и поймем, как она составлена.

В этой таблице все простые числа меньше 48 отмечены оранжевым цветом . Найдены они так:

• 1 – имеет единственный делитель и поэтому не является простым числом;
• 2 – наименьшее простое число и единственное четное, так как все остальные четные числа делятся на 2, то есть имеют не меньше 3 делителей, эти числа сведены в фиолетовую колонку ;
• 3 – простое число, имеет два делителя, все остальные числа, которые делятся на 3, исключаются – эти числа сведены в желтую колонку . Колонка, отмеченная и фиолетовым , и желтым , содержит числа делящиеся и на 2 и на 3;
• 5 – простое число, все числа, которые делятся на 5, исключаются – эти числа обведены зеленым овалом ;
• 7 – простое число, все числа, которые делятся на 7, обведены красным овалом – они не являются простыми;

Все числа не являющиеся простыми отмечены синим цветом . Далее эту таблицу можно составить самому по образу и подобию.

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

Приведем последовательность простых чисел начиная с 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, 109, 113, ... и т.д.

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

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

Одним из самых древних и эффективных способов вычисления простых чисел является «решето Эрастофена».

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

Кстати сказать, что для некоторых классов чисел существуют специализированные эффективные тесты простоты. К примеру, для проверки чисел Мерсенна на простоту применяют тест Люка-Лемера, а для проверки на простоту чисел Ферма - тест Пепина.

Все мы знаем, что чисел бесконечно много. Справедливо возникает вопрос: сколько же тогда существует простых чисел? Простых чисел также бесконечное количество. Наиболее древним доказательством этого суждения является доказательство Евклида, которое изложено в «Началах». Доказательство Евклида имеет следующий вид:

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

Теорема распределения простых чисел утверждает, что количество простых чисел меньших n, обозначаемое π(n), растёт как n / ln(n).

За тысячи лет исследования простых чисел, было выявлено, что наибольшим известным простым числом является 243112609 − 1. Это число включает 12 978 189 десятичных цифр и является простым числом Мерсенна (M43112609). Это открытие было сделано 23 августа 2008 года на математическом факультете университета uCLA в рамках проекта по распределённому поиску простых чисел Мерсенна GIMPS.

Главной отличительной особенностью чисел Мерсенна является наличие высоко эффективного теста простоты Люка - Лемера. С его помощью простые числа Мерсенна на протяжении длительного периода времени являются самыми большими из известных простых чисел.

Однако по сей день многие вопросы относительно простых чисел не получили точных ответов. На 5-м Международном математическом конгрессе Эдмунд Ландау сформулировал основным проблемы в области простых чисел:

Проблема Гольдбаха или первая проблема Ландау заключается в том, что необходимо доказать или опровергнуть, что каждое чётное число, большее двух, может быть представлено в виде суммы двух простых чисел, а каждое нечётное число, большее 5, может быть представлено в виде суммы трёх простых чисел.
Вторая проблема Ландау требует найти ответ на вопрос: бесконечно ли множество «простых близнецов» - простых чисел, разность между которыми равна 2?
Гипотеза Лежандра или третья проблема Ландау такова: верно ли, что между n2 и (n + 1)2 всегда найдётся простое число?
Четвёртая проблема Ландау: бесконечно ли множество простых чисел вида n2 + 1?
Помимо вышеперечисленных проблем существует проблема определения бесконечного количества простых чисел во многих целочисленных последовательностях типа числа Фибоначчи, числа Ферма и т. д.