Таблица Простых Чисел Поделиться Опции

[TiRexxx]

Давно пора модерам тему вынести в подфорум.


Недавно нашел таблицу простых чисел до 10 000 000 - может пригодится?

[Random]

Давно пора модерам тему вынести в подфорум.

Так она там и была...

[Паук]

эх, таблица...
Была бы она для 512-битных чисел...

[TiRexxx]

эх, таблица...
Была бы она для 512-битных чисел...

К сожалению нет :)
Однако из всех 512 битных чисел можно отсеять те, что делятся на числа из таблицы :)
(по принципу решета Эратосфена)

[TiRexxx]

Может кто-нибудь выложит число n в десятичном формате?

[DjSens]

Вот наше число в десятичном формате:
11823145941916446514690314500050400455024662194481817715418438557041820322734289
09890011957946150980589602953959112751256719731495098993655713709032459045266537
82569107413713350676232517817181096197654912904839291926811339932095007870787885
454476302964474574702429307332034331743839073902303658693917468638573
------------------
а простых 512-битных чисел больше чем атомов во всей вселенной. Без гонива. Чистая математика
------------------

прикрепляю то же число в виде файла

[10111]

----------------------------------------------------------------------------------------------------------------
Помогите мне найти таблицу простых чисел до 100.000.000.


Сообщение отредактировал 10111 - 5.4.2010, 7:12

[E2008]

----------------------------------------------------------------------------------------------------------------
Помогите мне найти таблицу простых чисел до 100.000.000.

§ 1. Основные понятия и теоремы
Пункт 6. Простые числа и "основная" теорема арифметики.

Определение. Число р О N , р № 1, называется простым, если р имеет в точности два положительных делителя: 1 и р . Остальные натуральные числа (кроме 1) принято называть составными. Число 1 - на особом положении, по договору, оно ни простое, ни составное.

Как это часто бывает в математике, да и в других науках, прилагательным "простой" называется объект только первоначально казавшийся простым. Простые числа, как выяснилось в процессе накопления научных знаний, появляются в различных областях математики и являются одним из самых загадочных и тяжелых для изучения монстров. Любопытного читателя, любителя ужастиков и лихо закрученных сюжетов, я отсылаю здесь к изумительному рассказу математика из Боннского университета Дон Цагира "Первые пятьдесят миллионов простых чисел", опубликованному в книжке "Живые числа", М.: Мир, 1985 г.

Отметим некоторые несложные наблюдения, связанные с простыми числами.

Наблюдение 1. Наименьший делитель любого числа а О N , отличный от 1, есть число простое.

Доказательство. Пусть с | а , с № 1 и с - наименьшее с этим свойством. Если существует с 1 такое, что с 1 | с , то с 1 Ј с и с 1 | а , следовательно, с 1 = с или с 1 = 1.

Ё

Наблюдение 2. Наименьший отличный от 1 делитель составного числа а О N не превосходит Ц a .

Доказательство. с | а , с № 1, с - наименьший, следовательно

а = са 1 , а 1 | а , а 1 і с , значит аа 1 і с 2 а 1 , а і с 2 и с Ј Ц a .

Ё

Следующее наблюдение, отдавая дань уважения его автору - Евклиду, назовем теоремой.

Теорема (Евклид). Простых чисел бесконечно много.

Доказательство. От противного. Ну пусть р 1 , р 2 ,..., р n - все простые, какие только есть. Рассмотрим число а = р 1 р 2 ... р n + 1. Его наименьший отличный от 1 делитель с , будучи простым, не может совпадать ни с одним из р 1 , р 2 ,..., р n , так как иначе с | 1. Не перестаю удивляться изобретательности ума людей тысячелетней древности!

Ё

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

2, 3, 4 , 5, 6 , 7, 8 , 9 , 10 , 11, 12 , 13, 14 , 15 , 16 , 17,...

Идем по натуральному ряду слева направо. Подчеркиваем первое неподчеркнутое и невычеркнутое число, а из дальнейшего ряда вычеркиваем кратные только что подчеркнутому. И так много раз. Легко понять, что подчеркнутые числа - простые. Если вспомнить наблюдение 2, то становится понятно, что когда вычеркнуты все кратные простых, меньших р , то оставшиеся невычеркнутые, меньшие р 2 - простые. Это значит, что составление таблицы всех простых чисел меньших N закончено сразу, как только вычеркнуты все кратные простых, меньших Ц a .

Для чисел, растущих закономерно, например для квадратов или степеней двойки, было бы, конечно, нелепо разыскивать экземпляр, превосходящий все известные. Для простых же чисел, напротив, прилагаются громадные усилия, чтобы именно это и сделать. Чудаки люди! Например, в 1876 году француз Люка доказал, что число 2 127 - простое, и 75 лет оно оставалось наибольшим из известных простых чисел, что не покажется удивительным, если на него взглянуть:

2 127 -1 = 170141183460469231731687303715884105727.

В настоящее время составлены таблицы всех простых чисел, не превосходящих 50 миллионов, далее известны только отдельные их представители. Читателей всегда привлекает гигантизм, поэтому укажу здесь два самых больших известных на сегодняшний момент простых числа: 2 44497 - 1 и 2 86243 - 1. Последнее число записано пока в книгу рекордов Гиннеса, в нем 25962 десятичных знака. Найдено оно было, конечно, в рекламных целях - демонстрация фирмой IBM возможностей очередного суперкомпьютера, которому для проверки этого числа на простоту с помощью специальных изощренных тестов (пригодных только для чисел вида 2 n- 1) потребовалась неделя работы и куча денег. И это трата денег происходит в то время, когда у нас в России более трети населения живет за чертой бедности, а половина детей в Уганде не умеют ни читать, ни писать, а только сидят и гундят!

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

Теорема. Всякое целое число, отличное от - 1, 0 и 1, единственным образом (с точностью до порядка сомножителей) разложимо в произведение простых чисел.

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

Пусть а > 1, р 1 - его наименьший простой делитель. Значит,

а = р 1 а 1 . Если, далее, а 1 > 1, то пусть р 2 - его наименьший простой делитель и а 1 = р 2 а 2 , т.е. а = р 1 р 2 а 2 , и так далее, пока а n не станет равным единице. Это обязательно произойдет, так как а > а 1 > а 2 ..., а натуральные числа с естественным порядком удовлетворяют условию обрыва убывающих цепей (во как выразился!). Имеем, таким образом,

a = p 1 p 2 ... p n , и возможность разложения доказана.

Покажем единственность. Ну пусть a = q 1 q 2 ... q n - другое разложение, т.е. p 1 p 2 ...p n = q 1 q 2 ...q s . В последнем равенстве правая часть делится на q 1 , следовательно, левая часть делится на q 1 . Покажем, что если произведение p 1 p 2 ...p n делится на q 1 , то один из сомножителей р k обязан делиться на q 1 .

Действительно, если q 1 | p 1 , то все доказано. Пусть q 1 не делит p 1 . Так как q 1 - простое число, то ( q 1 , p 1 ) = 1. Значит найдутся такие

u , v О Z , что up 1 + vq 1 = 1. Умножим последнее равенство на p 2 ...p n , получим: p 2 ... p n = p 1 ( p 2 ... p n ) u + q 1 ( p 2 ... p n ) v . Оба слагаемых справа делятся на q 1 , следовательно, p 2 ...p n делится на q 1 . Далее рассуждайте по индукции сами.

Теперь пусть, например, q 1 | p 1 . Значит q 1 = p 1 , так как p 1 - простое. Из равенства p 1 p 2 ...p n = q 1 q 2 ...q s банальным сокращением моментально получим равенство p 2 ...p n = q 2 ...q s . Снова рассуждая по индукции, видим, что n = s , и каждый сомножитель левой части равенства p 1 p 2 ...p n = q 1 q 2 ...q n обязательно присутствует в правой и наоборот.

Ё

Сразу отмечу без доказательства два достаточно очевидных следствия из этой теоремы.

Следствие 1. Всякое рациональное число однозначно представимо в виде p a 1
1 p a 2
2 ... p a k
k ,


где a 1 , a 2 ,..., a k О Z .

Ё

Следствие 2. Если a = p a 1
1 p a 2
2 ... p a n
n , b = p b 1
1 p b 2
2 ... p b n
n


- целые числа, то наибольший общий делитель a и b равен p g 1
1 p g 2
2 ... p g n
n ,


а наименьшее общее кратное a и b равно p d 1
1 p d 2
2 ... p d n
n ,


где g i = min { a i , b i }, a d i = max { a i , b i }.

Ё

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

Плохой пример. Пусть S = {4 k + 1 | k О Z } - множество вот таких вот целых чисел. Легко проверить, что S замкнуто относительно умножения:

(4 k 1 + 1)·(4 k 2 + 1) = 16 k 1 k 2 + 4 k 2 + 4 k 1 + 1 = 4·(4 k 1 k 2 + k 1 + k 2 ) + 1 О S ,

однако это множество не замкнуто относительно сложения. "Квазипростые" числа из S - суть далее неразложимые в произведение чисел из S : 5, 9, 13, 17, 21, 49,... Индуктивным рассуждением, подобным рассуждению в первой части доказательства основной теоремы арифметики, легко убедиться, что всякое число из S разложимо в произведение "квазипростых". Однако единственность такого разложения отсутствует: 441 = 21·21 = 9·49, при этом 9 не делит 21, и 49 не делит 21. Вот какой плохой пример. Задачки
1 . Простое число - это число, имеющее в точности два различных положительных делителя (единицу и себя). Найдите все натуральные числа, имеющие в точности

а) три различных положительных делителя;

б) четыре различных положительных делителя;

в) k штук различных положительных делителей ( k > 4).

2 . Опоссум Порфирий в зоопарке раскладывает на простые множители число 81 057 226 635 000. Помогите ему, не то он обидится.

3 . Методом Эратосфена составьте таблицу простых чисел, меньших 100.

4 . Докажите, что среди членов каждой из арифметических прогрессий:

а) 3, 7, 11, 15, 19,...

б) 5, 11, 17, 23, 29,...

в) 11, 21, 31, 41, 51,...

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

5 . Докажите, что в натуральном ряде имеются сколь угодно длинные промежутки вида { n , n +1, n +2, …, n + k }, не содержащие простых чисел.

6 . Докажите, что не существует такого многочлена f ( x ) = a 0 x n + a 1 x n -1 +…+ a n -1 x + a n с целыми коэффициентами, что все числа f (0), f (1), f (2), f (3), … являются простыми. **


* Оказывается, справедлив такой общий факт: Если первый член и разность арифметической прогрессии взаимно просты, то среди ее членов содержится бесконечно много простых чисел. Более того, ряд, составленный из обратных величин к этим простым числам, расходится. Это классическое утверждение называется теоремой Дирихле и доказывается весьма сложно. В 1950 году датский математик А. Сельберг придумал чрезвычайно сложное и хитроумное элементарное (не использующее аппарат высшей математики) доказательство теоремы Дирихле, однако жить лучше от этого не стало и даже сильно одаренному школьнику доказательство теоремы Дирихле вряд ли объяснишь.

** Абсолютно несложное доказательство этого факта впервые придумал Л. Эйлер. Он же напридумывал массу многочленов f ( x ), значения которых при многих последовательных натуральных x являются про-стыми числами. Два примера:

а) f ( x ) = x 2 + x +41, при x = 0, 1, 2, ... , 39.

б) f ( x ) = x 2 -79 x +1601, при x = 0, 1, 2, ... , 79.

Если же рассматривать многочлены от нескольких переменных, то, как следует из результатов Ю. В. Матиясевича о диофантовости рекурсивных множеств (опубликовано в 1970 году), существуют многочлены, множество положительных значений которых в точности является множеством всех про-стых чисел. Преследуя чисто спортивный интерес, укажу здесь один такой многочлен от 26 переменных:

F ( a , b , c , d , e , f , g , h , i , j , k , l , m , n , o , p , q , r , s , t , u , v , w , x , y , z ) =
= { k + 2}{1 - ( wz + h + j - q ) 2 - (2 n + p + q + z - e ) 2 -
- ( a 2 y 2 - y 2 + 1 - x 2 ) 2 -({ e 4 + 2 e 3 }{ a + 1} 2 - o 2 ) 2 -
- (16{ k + 1} 3 { k + 2}{ n + 1} 2 + 1 - f 2 ) 2 -
- ({( a + u 4 - u 2 a ) 2 - 1}{ n + 4 dy } 2 + 1 - { x + cu } 2 ) 2 - ( ai + k + 1 - l - i ) 2 -
- ({ gk + 2 g + k + 1}{ h + j } + h - z ) 2 - (16 r 2 y 4 { a 2 - 1} + 1 - u 2 ) 2 -
- ( p - m + l { a - n - 1} + b {2 an + 2 a - n 2 - 2 n - 2}) 2 -
- ( z - pm + pla - p 2 l + t {2 ap - p 2 - 1}) 2 -
- ( q - x + y { a - p - 1} + s {2 ap + 2 a - p 2 - 2 p - 2}) 2 -
- ( a 2 l 2 - l 2 + 1 - m 2 ) 2 - ( n + l + v - y ) 2 }