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

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

Давеча снова увлекся простыми числами. Манит меня их тайна.

Написал алгоритм, похожий на решето Эратосфена. За 3 часа программа нашла 700 тысяч первых простых чисел. А мне надо хотя бы 14 миллионов простых чисел, чтобы перемножив их, получить число с количеством десятичных цифр, равным 100 миллионам штук.

Из статьи «Еще раз о поиске простых чисел», написанной пользователем Bodigrim, узнал о существовании быстрой программы primegen, которая работает используя решето Аткина. Установил ее в виртуальной машине LUbuntu (VirtualBox). Действительно, primegen очень быстро работает!

Тогда встал вопрос, как сохранить 14 миллионов простых чисел? Можно просто каждое простое число записать в файл как int32. А если простое число будет больше мощности 32-х бит?

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

Осталось узнать максимально-возможное расстояние для определенного диапазона чисел. Поскольку разница между простыми числами всегда есть четное число (кроме расстояния между 2 и 3), то разделим расстояние на 2.

В программе primegen в исходном файле primes.c вместо вывода числа на экран реализовал алгоритм подсчета статистики по кол-ву расстояний между числами:

В терминале выполнил:

Через 10 секунд отобразился список:

0 = 1 (расстояние между числами 2 и 3)
1 = 3424507

141 = 1

Таким образом, 141 — максимально-возможное расстояние по простое число значением до 1 миллиарда.

Написал код записи в файл:

Запустил до 300 миллионов:

В файле primes.bin получил 16 миллионов первых простых чисел. Сжал архиватором 7-Zip, файл ужался до 9 Мб.

P.S. Есть идея, как еще сильнее сжать БД простых чисел. Надо простые числа разделить на 4 группы по последней десятичной цифре: 1, 3, 7, 9. Расстояние между числами делить на 10. Так же сформировать 4 файла. При этом возможно, что для значений расстояния можно будет отвести не 8 бит, а меньше, тогда придется реализовать формирование байтового буфера из, например, 5-битных расстояний.

Читайте также:  Повтор экрана iphone на телевизоре lg

Хотя в наш век Гигабайтных емкостей это не сильно принципиально.

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

Пример: 5 можно разделить, чтоб не было остатка только на 1 и на 5;

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

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 127 131
137 139 149 151 157 163 167 173
179 181 191 193 197 199 211 223
227 229 233 239 241 251 257 263
269 271 277 281 283 293 307 311
313 317 331 337 347 349 353 359
367 373 379 383 389 397 401 409
419 421 431 433 439 443 449 457
461 463 467 479 487 491 499 503
509 521 523 541 547 557 563 569
571 577 587 593 599 601 607 613
617 619 631 641 643 647 653 659
661 673 677 683 691 701 709 719
727 733 739 743 751 757 761 769
773 787 797 809 811 821 823 827
829 839 853 857 859 863 877 881
883 887 907 911 919 929 937 941
947 953 967 971 977 983 991 997

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

Как пользоваться таблицей? Всё гораздо просто, все приведенные тут числа в конкретном диапазоне от 1 до 1000, являются простыми.

Читайте также:  Тревога переназначенные сектора что делать

1 это простое число?

Часто звучит вопрос «А почему здесь нет единицы? Нет это не ошибка и даже не опечатка. Следует внести понимание по поводу числа 1, оно имеет всего один делитель, потому его принято вовсе не относить ни к простым, ни к составным числам.

* На практике, например для ученика 6 класса обычно при решении школьных задачек и при математических расчётах вполне достаточно табличных данных от 1 до 100, крайне редко приходится прибегать к более развернутым спискам. Исходя из этого определения и сформирована эта полная таблица из первых 168 простых чисел.

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

Ссылка на основную публикацию
Adblock detector