Сколько простых чисел до миллиарда

Ищем простые числа до триллиона за тридцать минут

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

Сегодня я хотел бы поделиться с вами различными вариантами реализации поиска простых чисел на языке C#, начиная с классических алгоритмов — решета Эратосфена, Сундарама и Аткина, и кончая различными оптимизациями (сегментация, факторизация). Особый упор я делал на простоту: самый быстрый из алгоритмов, который мне удалось получить, содержит 120 строк кода и ищет простые числа до триллиона меньше, чем за 30 минут, а до миллиарда — меньше, чем за секунду (это далеко от производительности лучших из существующих библиотек по поиску простых чисел, но эти библиотеки обычно содержат свыше 4000 строк кода).
В заключение мы применим самую быструю реализацию для поиска максимального расстояния между двумя соседними простыми числами до триллиона. Прежде чем заходить под кат, я предлагаю вам попытаться угадать ответ. Для сравнения, для простых чисел до 100 максимальное растояние равно 8 (между соседними простыми числами 89 и 97), а до тысячи — 20 (между 887 и 907).

Весь исходный код можно найти на гитхабе.

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

Решето Эратосфена — самый простой и известный алгоритм для поиска простых чисел. Его суть состоит в следующем:

Выписываем числа 2, 3, . N;
Берем первое число в списке и вычеркиваем из списка все числа, кратные ему, начиная с : 4, 6, 8, .
Берем следующее число в списке и вычеркиваем кратные ему 9, 15, .
Продолжаем процедуру для каждого последующего числа из оставшихся в списке пока выполняется неравенство ; оставшиеся после этого в списке числа и будут простыми:

Поскольку наша задача — сравнить между собой разные реализации поиска простых чисел, мы наследуем все варианты от интерфейса ISieve, имеющего только один метод:

Для перечисления простых чисел был выбран способ колбеков, а не более привычные для C# энумераторы, поскольку он на 10-40% быстрее. Этот интерфейс позволяет единообразно тестировать разные реализации и сравнивать их между собой; в частности, мы будем считать количество, сумму и хеш простых чисел до миллиарда:

Алгоритм: решето Эратосфена
Ищет простые числа до миллиарда: 12.6 секунд.

2. Решето Сундарама

После этого, для оставшихся в списке чисел , последовательность чисел будет представлять все нечетные простые числа до N.

вычеркиваем 1+j+2*1*j: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, . ]
вычеркиваем 2+j+2*2*j: [1, 2, 3, 5, 6, 8, 9, 11, 12, 14, 15, . ]
вычеркиваем 3+j+2*3*j: [1, 2, 3, 5, 6, 8, 9, 10, 11, 14, . 24, . ]
и так далее.
последовательность 2n+1: [3, 5, 7, 11, 13, 17, 19, . ]

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

Алгоритм: решето Сундарама
Ищет простые числа до миллиарда: 18 секунд.

3. Решето Аткина

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

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

Практическая реализация рассматривает числа , не делящиеся на 2, 3, 5, и имеющие определенные остатки от деления на 60.

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

Алгоритм: решето Аткина

Ищет простые числа до миллиарда: 11.4 секунд.

4. Колёсная факторизация

Колёсная факторизация — вид оптимизации решета Эратосфена, позволяющий заранее исключить из рассмотрения числа, заведомо не являющиеся простыми. Например, любое простое число, большее 6, имеет остаток от деления на 6 либо 1, либо 5: или : при любых других остатках число будет делиться либо на 2, либо на 3. Аналогично, простое число, большее , может иметь только один из 8 остатков от деления на 30: . Еще одно преимущество оптимизации — уменьшение потребения памяти: вместо одного бита на число для решета Эратосфена или 0.5 бит на число для решета Сундарама, факторизация с базой требует примерно 0.27 бит на число, поскольку позволяет хранить 30 чисел в 8 битах. При аккуратном применении оптимизация позволяет ускорить просеивание в несколько раз, однако неоптимизированные варианты обычно работают медленно за счет большей сложности. В прошлой публикации я подробно описывал алгоритм, однако он не был оптимизирован по производительности, поэтому здесь я приведу более простой и эффективный вариант.

Алгоритм: (2,3,5)-факторизация
Ищет простые числа до миллиарда: 9.6 секунд.

5. Оптимизированное решето Эратосфена

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

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

Эта оптимизация дает нам практически двукратный выигрыш в производительности, и, кроме того, требует 0.5 бита на натуральное число, как и решето Сундарама.

Алгоритм: Оптимизированное решето Эратосфена
Ищет простые числа до миллиарда: 6.6 секунд.

6. Оптимизированное решето Сундарама

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

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

Производительность, что не удивительно, совпадает с предыдущим алгоритмом:

Алгоритм: Оптимизированное решето Сундарама
Ищет простые числа до миллиарда: 6.5 секунд.

7. Сегментированное решето Эратосфена

Все предыдущие алгоритмы хранили весь результат в памяти, что ограничивает их применение небольшими диапазонами. Например, при поиске простых чисел до триллиона, решето Эратосфена будет требовать 120 гигабайт оперативной памяти; кроме того, его скорость будет деградировать, так как просеивание (вычеркивание составных чисел) бегает по всему массиву, не эффективно используя кеши процессора.

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

вычеркиваем кратные 2: [ 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90]
вычеркиваем кратные 3: [ 81, 83, 85, 87, 89]
вычеркиваем кратные 5: [83, 85, 89]
вычеркиваем кратные 7 (нет в интервале): [83, 89]
Этот подход называется сегментированное решето, и с его применением требования к памяти снижаются с до . На практике размер интервалов выбирают либо равным , либо зависящим от размера кеша процессора.

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

Алгоритм: Сегментированное решето Эратосфена
Ищет простые числа до миллиарда: 8.6 секунд.

8. Оптимизированное сегментированное решето

Данная оптимизация относится к «народной» — она широко известна, но, похоже, не имеет своего названия. Цель оптимизации — избавиться от арифметического выражения, вычисляющего первое число в сегменте, кратное простому числу . Так как сегментированное решето обрабатывает сегменты подряд в порядке возрастания, нетрудно убедиться, что нужное число будет равно первому числу, кратному , выхожящему за граниы предыдущего сегмента. Таким образом, нам достаточно для каждого простого числа хранить текущее кратное ему число. В упрощенном виде это можно представить так:

Полная реализация с небольшими дополнительными оптимизациями позволяет ускорить предыдущий алгоритм примерно на 20%

Алгоритм: Оптимизированное сегментированное решето
Ищет простые числа до миллиарда: 7.1 секунд.

9. Сегментированная факторизация с базой 2

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

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

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

Алгоритм: Сегментированная факторизация с базой 2
Ищет простые числа до миллиарда: 3.4 секунды.

10. Сегментированная (2,3)-факторизация

В предыдущей реализации мы исключили из рассмотрения числа, делящиеся на два; теперь исключим числа, делящиеся на 2 и 3. Тогда оставшиеся числа делятся на два класса: дающие 1 или 5 в остатке от деления на 6. Поэтому вместо одного битового массива используем два: PrimeMultiples_6kPlus1 и PrimeMultiples_6kPlus5; они будут хранить числа вида и для чисел, кратных , имеющих 1 или 5 в остатке от деления на 6. Дополнительные усилия нужны, чтобы найти первое число вида , имеющее нужный остаток от деления на 6, но это решается простым перебором .

Алгоритм: Сегментированная (2,3)-факторизация
Ищет простые числа до миллиарда: 2.6 секунды.

11. Сегментированная (2,3,5)-факторизация

Применим ту же идею для чисел, не делящихся на 2, 3 и 5. Тогда у нас будет не два битовых массива, а восемь, по одному на каждый остаток от деления на 30: . В остальном код не особо изменится, и даст нам еще небольшое ускорение.

Алгоритм: Сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 2.3 секунды.

12. Оптимизированная сегментированная (2,3,5)-факторизация

Факторизация позволяет уменьшить количество чисел, которые мы вычеркиваем, но вычисление индекса байта и бита в битовом массиве (как при просеивании, так и при повторном проходе по массиву для перечисления простых чисел) все равно занимает большую часть времени. Поэтому воспользуемся уже знакомым нам трюком, пользуясь тем, что в факторизации с базой (2,3,5) восемь остатков: вместо восьми битовых массивов используем один массив байт, в котором каждый из восьми бит отвечает за свой остаток от деления на 30. Это позволит нам в массиве PrimeMultiples держать индекс байта, а индекс бита будет постоянным. Тогда внутренний цикл просеивания становится исключительно простым:

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

Тогда получение простых чисел сводится к простому циклу:

Эта оптимизация ускоряет предыдущую реализацию больше, чем в два раза, позволяя найти простые числа до миллиарда меньше, чем за секунду!

Алгоритм: Оптимизированная сегментированная (2,3,5)-факторизация
Ищет простые числа до миллиарда: 0.93 секунды.

Максимальное расстояние между простыми числами до триллиона

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

Результат работы программы:

Простые числа до 1,000,000,000,000
Время работы: 26 минут 30 секунд
Максимальное расстояние между простыми числами: 540
между 738,832,927,927 и 738,832,928,467

Лучшие библиотеки

Рассказ был бы не полон без сравнения с лучшими из существующих библиотек по поиску простых чисел.

Самая известная библиотека — primegen, основанная на сильно оптимизированном решете Аткина. Она написана на C самим Даниэлем Бернштейном (соавтором Аткина) 20 лет назад и оптимизирована под Пентиум, поэтому для эффективного ее использования требуется поменять размер буфера в файле conf-words:

На моем ноутбуке наилучшая производительность достигается при установке буфера 65536 байт. В библиотеку входит утилита primegaps, которая как раз и ищет максимальное расстояние между простыми числами. Время ее работы для простых чисел до триллиона — 19 минут.

Но на данный момент, пожалуй, самая быстрая библиотека — primesieve, написанная на c++ и включающая огромное количество оптимизаций, включая различные стратегии просеивания для маленьких, средних и больших простых чисел, автоматическое определение размера кешей процессора и многопоточность. На моем ноутбуке программа ищет простые числа до триллиона в 8 потоков за 70 секунд. Автор библиотеки Kim Walish подробно описывает оптимизации в коде, поэтому эта библиотека отлично подходит для изучения самых лучших на сегодняшний день оптимизаций и для практического применения.

Сколько простых чисел до миллиарда

10^<18>» width=»» height=»» />. Это составляет 24 739 954 287 740 860 простых чисел, но они не были сохранены. Существуют известные формулы, позволяющие вычислить количество простых чисел (до заданного значения) быстрее, чем вычисление самих простых чисел. Этот способ был использован, чтобы вычислить, что до <img decoding=

Проект по проверке проблемы Гольдбаха сообщает, что были вычислены все простые числа до

Простые числа вида $\frac<x^3 - y^3><x - y>, x = y + 1 » width=»» height=»» /></p> <p>7, 19, 37, 61, 127, 271, 331, 397, 547, 631, 919, 1657, 1801, 1951, 2269, 2437, 2791, 3169, 3571, 4219, 4447, 5167, 5419, 6211, 7057, 7351, 8269, 9241, 10267, 11719, 12097, 13267, 13669, 16651, 19441, 19927, 22447, 23497, 24571, 25117, 26227, 27361, 33391, 35317 (последовательность A002407 в OEIS).</p> <p>а также <img decoding=$ делится нацело на p^2 .

$<<2p-1>\choose<p-1>> \equiv 1 \pmod<p^4>» width=»» height=»» />.</p> <p>Известны только эти числа до миллиарда: 16843, 2124679 (последовательность A088164 в OEIS)</p> <h3>Простые числа Кэрола</h3> <p><img decoding=$

Простые числа p для которых биномиальный коэффициент

7, 47, 223, 3967, 16127, 1046527, 16769023, 1073676287, 68718952447, 274876858367, 4398042316799, 1125899839733759, 18014398241046527, 1298074214633706835075030044377087 (последовательность A091516 в OEIS).

x^2 + y^2 + p^2 = 3xyp

2^n - 1

3, 7, 31, 127, 8191, 131071, 524287, 2147483647, 2305843009213693951, 618970019642690137449562111, 162259276829213363391578010288127, 170141183460469231731687303715884105727 (последовательность A000668 в OEIS).

Простые числа вида $P=k \cdot 2^n+1$ , причем нечетно и 2^n>k (последовательность A080076 в OEIS).

2, 3, 5, 11, 23, 29, 41, 53, 83, 89, 113, 131, 173, 179, 191, 233, 239, 251, 281, 293, 359, 419, 431, 443, 491, 509, 593, 641, 653, 659, 683, 719, 743, 761, 809, 911, 953 (последовательность A005384 в OEIS).

Это простые числа вида 2^<2^n>+ 1″ width=»» height=»» />.</p> <p>Известные числа Ферма: 3, 5, 17, 257, 65537 (последовательность A019434 в OEIS).</p> <h3>Простые числа Чена</h3> <p>Такие простые числа <img decoding= , что p+2 либо простое, либо полупростое.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 47, 53, 59, 67, 71, 83, 89, 101, 107, 109, 113, 127, 131, 137, 139, 149, 157, 167, 179, 181, 191, 197, 199, 211, 227, 233, 239, 251, 257, 263, 269, 281, 293, 307, 311, 317, 337, 347, 353, 359, 379, 389, 401, 409 (последовательность A109611 в OEIS)

5, 53, 157, 173, 211, 257, 263, 373, 563, 593, 607, 653, 733, 947, 977, 1103, 1123, 1187, 1223, 1367, 1511, 1747, 1753, 1907, 2287, 2417, 2677, 2903, 2963, 3307, 3313, 3637, 3733, 4013, 4409, 4457, 4597, 4657, 4691, 4993, 5107, 5113, 5303, 5387, 5393 (последовательность A006562 в OEIS)

Простые числа p, длина периодической дроби которых от $\frac<1> </p> <p>» width=»» height=»» /> уникальна (ни одно другое простое число не даёт такое же).</p> <p>3, 11, 37, 101, 9091, 9901, 333667, 909091, 99990001, 999999000001, 9999999900000001, 909090909090909091, 1111111111111111111, 11111111111111111111111, 900900900900990990990991 (последовательность A040017 в OEIS).</p> <h3>Факториальные простые</h3> <p>Это простые числа вида <img decoding=$ для некоторого $n\in<\Bbb N>» width=»» height=»» />.</p> <p>2, 3, 5, 7, 23, 719, 5039, 39916801, 479001599, 87178291199, 10888869450418352160768000001, 265252859812191058636308479999999, 263130836933693530167218012159999999, 8683317618811886495518194401279999999 (последовательность A088054 в OEIS).</p> <h3>Центральные квадратные простые числа</h3> <p><img decoding=$

5, 13, 41, 61, 113, 181, 313, 421, 613, 761, 1013, 1201, 1301, 1741, 1861, 2113, 2381, 2521, 3121, 3613, 4513, 5101, 7321, 8581, 9661, 9941, 10513, 12641, 13613, 14281, 14621, 15313, 16381, 19013, 19801, 20201, 21013, 21841, 23981, 24421, 26681 (последовательность A027862 в OEIS)

(3n^2+3n+2)/2

19, 31, 109, 199, 409, 571, 631, 829, 1489, 1999, 2341, 2971, 3529, 4621, 4789, 7039, 7669, 8779, 9721, 10459, 10711, 13681, 14851, 16069, 16381, 17659, 20011, 20359, 23251, 25939, 27541, 29191, 29611, 31321, 34429, 36739, 40099, 40591, 42589 (последовательность A125602 в OEIS)

(7n^2-7n+2)/2

43, 71, 197, 463, 547, 953, 1471, 1933, 2647, 2843, 3697, 4663, 5741, 8233, 9283, 10781, 11173, 12391, 14561, 18397, 20483, 29303, 29947, 34651, 37493, 41203, 46691, 50821, 54251, 56897, 57793, 65213, 68111, 72073, 76147, 84631, 89041, 93563 (последовательность A069099 в OEIS)

5(n^2-n)+1

11, 31, 61, 101, 151, 211, 281, 661, 911, 1051, 1201, 1361, 1531, 1901, 2311, 2531, 3001, 3251, 3511, 4651, 5281, 6301, 6661, 7411, 9461, 9901, 12251, 13781, 14851, 15401, 18301, 18911, 19531, 20161, 22111, 24151, 24851, 25561, 27011, 27751 (последовательность A090562 в OEIS)

↑A Search for Wilson primes

Генри С. Уоррен, мл. Глава 16. Формулы для простых чисел // Алгоритмические трюки для программистов = Hacker’s Delight. — М .: Вильямс, 2007. — 288 с. — ISBN 0-201-91465-4

Целочисленные последовательности
Списки чисел

Wikimedia Foundation . 2010 .

Простые числа до 10000000000000 список

Сумма цифр	1
Произведение цифр
Произведение цифр (без учета ноля)	1
Количество цифр в числе	14 (четырнадцатизначное число)
Все делители числа	1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250, 256, 320, 400, 500, 512, 625, 640, 800, 1000, 1024, 1250, 1280, 1600, 2000, 2048, 2500, 2560, 3125, 3200, 4000, 4096, 5000, 5120, 6250, 6400, 8000, 8192, 10000, 10240, 12500, 12800, 15625, 16000, 20000, 20480, 25000, 25600, 31250, 32000, 40000, 40960, 50000, 51200, 62500, 64000, 78125, 80000, 100000, 102400, 125000, 128000, 156250, 160000, 200000, 204800, 250000, 256000, 312500, 320000, 390625, 400000, 500000, 512000, 625000, 640000, 781250, 800000, 1000000, 1024000, 1250000, 1280000, 1562500, 1600000, 1953125, 2000000, 2500000, 2560000, 3125000, 3200000, 3906250, 4000000, 5000000, 5120000, 6250000, 6400000, 7812500, 8000000, 9765625, 10000000, 12500000, 12800000, 15625000, 16000000, 19531250, 20000000, 25000000, 25600000, 31250000, 32000000, 39062500, 40000000, 48828125, 50000000, 62500000, 64000000, 78125000, 80000000, 97656250, 100000000, 125000000, 128000000, 156250000, 160000000, 195312500, 200000000, 244140625, 250000000, 312500000, 320000000, 390625000, 400000000, 488281250, 500000000, 625000000, 640000000, 781250000, 800000000, 976562500, 1000000000, 1220703125, 1250000000, 1562500000, 1600000000, 1953125000, 2000000000, 2441406250, 2500000000, 3125000000, 3200000000, 3906250000, 4000000000, 4882812500, 5000000000, 6250000000, 7812500000, 8000000000, 9765625000, 10000000000, 12500000000, 15625000000, 16000000000, 19531250000, 20000000000, 25000000000, 31250000000, 39062500000, 40000000000, 50000000000, 62500000000, 78125000000, 80000000000, 100000000000, 125000000000, 156250000000, 200000000000, 250000000000, 312500000000, 400000000000, 500000000000, 625000000000, 1000000000000, 1250000000000, 2000000000000, 2500000000000, 5000000000000, 10000000000000
Наибольший делитель из ряда степеней двойки	8192
Количество делителей	196
Сумма делителей	24998474116998
Простое число?	Нет
Полупростое число?	Нет
Обратное число	1e-13
Индо-арабское написание	١٠٠٠٠٠٠٠٠٠٠٠٠٠
Азбука морзе

Описание числа 10000000000000

Натуральное рациональное четное число 10000000000000 является составным. Произведение цифр: 0. Делители числа 10000000000000: 1, 2, 4, 5, 8, 10, 16, 20, 25, 32, 40, 50, 64, 80, 100, 125, 128, 160, 200, 250, 256, 320, 400, 500, 512, 625, 640, 800, 1000, 1024, 1250, 1280, 1600, 2000, 2048, 2500, 2560, 3125, 3200, 4000, 4096, 5000, 5120, 6250, 6400, 8000, 8192, 10000, 10240, 12500, 12800, 15625, 16000, 20000, 20480, 25000, 25600, 31250, 32000, 40000, 40960, 50000, 51200, 62500, 64000, 78125, 80000, 100000, 102400, 125000, 128000, 156250, 160000, 200000, 204800, 250000, 256000, 312500, 320000, 390625, 400000, 500000, 512000, 625000, 640000, 781250, 800000, 1000000, 1024000, 1250000, 1280000, 1562500, 1600000, 1953125, 2000000, 2500000, 2560000, 3125000, 3200000, 3906250, 4000000, 5000000, 5120000, 6250000, 6400000, 7812500, 8000000, 9765625, 10000000, 12500000, 12800000, 15625000, 16000000, 19531250, 20000000, 25000000, 25600000, 31250000, 32000000, 39062500, 40000000, 48828125, 50000000, 62500000, 64000000, 78125000, 80000000, 97656250, 100000000, 125000000, 128000000, 156250000, 160000000, 195312500, 200000000, 244140625, 250000000, 312500000, 320000000, 390625000, 400000000, 488281250, 500000000, 625000000, 640000000, 781250000, 800000000, 976562500, 1000000000, 1220703125, 1250000000, 1562500000, 1600000000, 1953125000, 2000000000, 2441406250, 2500000000, 3125000000, 3200000000, 3906250000, 4000000000, 4882812500, 5000000000, 6250000000, 7812500000, 8000000000, 9765625000, 10000000000, 12500000000, 15625000000, 16000000000, 19531250000, 20000000000, 25000000000, 31250000000, 39062500000, 40000000000, 50000000000, 62500000000, 78125000000, 80000000000, 100000000000, 125000000000, 156250000000, 200000000000, 250000000000, 312500000000, 400000000000, 500000000000, 625000000000, 1000000000000, 1250000000000, 2000000000000, 2500000000000, 5000000000000, 10000000000000. Обратным числом является 1e-13.
Число 10000000000000 представляется произведением: 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5 * 5.

Сколько простых чисел до миллиарда

Ищем простые числа до триллиона за тридцать минут

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

2. Решето Сундарама

3. Решето Аткина

4. Колёсная факторизация

5. Оптимизированное решето Эратосфена

6. Оптимизированное решето Сундарама

7. Сегментированное решето Эратосфена

8. Оптимизированное сегментированное решето

9. Сегментированная факторизация с базой 2

10. Сегментированная (2,3)-факторизация

11. Сегментированная (2,3,5)-факторизация

12. Оптимизированная сегментированная (2,3,5)-факторизация

Максимальное расстояние между простыми числами до триллиона

Лучшие библиотеки

Сколько простых чисел до миллиарда

Простые числа до 10000000000000 список

Описание числа 10000000000000

Добавить комментарий Отменить ответ