sega333
Новичок
|
     
При расчёте по формуле n = 2*p +1 будет рассчитываться 50% чисел, а по формуле n = 6*p ±1 будет рассчитываться 33% чисел.
По поводу решета, возьмём такой пример простое число 300000007.
Если брать решето, то нужно 300000007*2, затем 300000007*3 и т.д.
По выведенным мной формулам исключений, для простого числа 300000007, первым исключением будет число 300000007*300000007=90000004200000049
Сколько лишних действий было-бы сделано, если считать по решету?
Затем по очереди прибавляются произведения n*2, n*4 или 90000004200000049 + n*2, 90000004200000049 + n*6, 90000004200000049 + n*8, 90000004200000049 +n*12, 90000004200000049 + n*14 и т.д.
Видно, что расчётов производится намного меньше (по решету 14, по выведенным формулам всего 5), нет ни одного лишнего действия.
Каждое найденное значение исключения, для каждого простого числа, нужно убрать из ряда полученного по формулам n = p * 6 – 1, n = p * 6 + 1.
И всё ряд простых чисел готов.
Согласен, что вряд-ли возможно с помощью моих формул добраться до 2^82`589`933 -1, на простом компьютере.
Формулы предназначены для планомерного расчёта ряда простых чисел.
(Сообщение отредактировал sega333 27 сен. 2022 7:05)
|
Всего сообщений: 6 | Присоединился: сентябрь 2022 | Отправлено: 26 сен. 2022 21:09 | IP
|
|
Alex_soldier
Новичок
|
sega333, вы описываете оптимизированное Решето Эратосфена.
Оно уже реализовано в современных программах-просеивателях.
n = 2*p +1 исключает 50% составных чисел (четные)
n = 6*p +[1,5] исключает 67% составных чисел (делятся и на 3)
n = 30*p +[1...29] исключает 73% составных чисел (делятся и на 5)
n = 210*p +[1...209] исключает 77% составных чисел (делятся и на 7)
n = 2310*p +[1...2309] исключает 79% составных чисел (делятся и на 11)
С одной стороны заманчиво продвигаться все дальше по праймориальной функции.
С другой - расплата: ряды множатся, в квадратных скобках становится все больше вариабельных чисел.
В GIMPS и ряде просеивающего ПО остановились именно на 2310.
|
Всего сообщений: 9 | Присоединился: июнь 2016 | Отправлено: 26 сен. 2022 21:47 | IP
|
|
sega333
Новичок
|
Извините, но не могли-бы вы мне подсказать по поводу n = 210*p +[1...209]
Я накидал програмку, но она считает не все простые числа например число 331 простое, а она его не рассчитывает. 331=210*1+121, а 121 это не простое число.
[1...209] - это простые числа, я правильно понимаю.
Если не сложно, поясните пожалуйста.
|
Всего сообщений: 6 | Присоединился: сентябрь 2022 | Отправлено: 29 сен. 2022 22:06 | IP
|
|
Alex_soldier
Новичок
|
Добрый вечер.
В квадратных скобках присутствуют только те числа, которые не имеют общих множителей (>1) с текущей функцией праймориала:
Для 2*p это только [1].
Для 6*p это [1,5].
Для 30*p это [1,7,11,13,17,19,23,29].
Для 210*p это [1,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,121,127,131,137,139,143,149,151,157,163,167,169,173,179,181,187,191,193,197,199,209].
Для 2310*p это [1,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,143,149,151,157,163,167,169,173,179,181,191,193,197,199,211,221,223,227,229,233,239,241,247...2291,2293,2297,2309].
И т.д.
|
Всего сообщений: 9 | Присоединился: июнь 2016 | Отправлено: 30 сен. 2022 0:08 | IP
|
|
sega333
Новичок
|
Благодарю!
Программу поправил, заработала как надо.
|
Всего сообщений: 6 | Присоединился: сентябрь 2022 | Отправлено: 30 сен. 2022 20:35 | IP
|
|
Alex_soldier
Новичок
|
Удачных вычислений!
А поиском больших (сотни тысяч знаков) Простых чисел не интересуетесь?
|
Всего сообщений: 9 | Присоединился: июнь 2016 | Отправлено: 30 сен. 2022 20:45 | IP
|
|
sega333
Новичок
|
Цитата: Alex_soldier написал 30 сен. 2022 20:45
Удачных вычислений!
А поиском больших (сотни тысяч знаков) Простых чисел не интересуетесь?
Извините, что долго не отвечал, всё занимался своими программами. Интересуюсь, но проверить, простое число или нет, на таких больших разрядах практически невозможно, нужны какие-то специальные алгоритмы или зависимости.
|
Всего сообщений: 6 | Присоединился: сентябрь 2022 | Отправлено: 23 окт. 2022 19:08 | IP
|
|
Alex_soldier
Новичок
|
sega333, с возвращением!
В конце 90х я и сам баловался написанием различных программ. Но получались в основном просеиватели для разных форм чисел, а вот доказательство простоты оставшихся кандидатов упиралось в потолок 18-19 знаков.
Уже в 2000х в интернете я наткнулся на ряд программ, позволяющих довольно шустро доказывать простоту чисел разного вида. Причем я осознал, что сам я такого же не напишу, поскольку их разработчики использовали аппаратную оптимизацию.
С тех пор пересел на уже зарекомендовавшие себя в сообществе программы, и нашел благодаря им довольно много результатов. Сейчас я потихоньку публикую их, как доходят руки, а также некоторые достижения других участников. Если интересно: prime-numbers ru
Вы не хотели бы попробовать свои силы (точнее - железо) в каком-либо поиске? По сути, это хороший способ остаться в истории математики - на сайте проектов обычно размещают имена тех, кто нашел что-то значимое, даже если это и не мировой рекод в своей категории.
|
Всего сообщений: 9 | Присоединился: июнь 2016 | Отправлено: 1 нояб. 2022 19:31 | IP
|
|
sega333
Новичок
|
Хорошо, я посмотрю.
|
Всего сообщений: 6 | Присоединился: сентябрь 2022 | Отправлено: 4 нояб. 2022 18:46 | IP
|
|
|
Форум
Простые числа
