Подскажите формулу для p_n

[qtrln]

Доброго времени суток. Правильно ли я понимаю, что здесь рунет-stackoverlow?

Я пишу проект по программированию в школе, и для нее мне срочно понадобилась формула для вычисления $n$-го простого числа. Проще говоря, требуется функция, которая берет на вход целое положительное число $n,$ а на выходе дает значение $n$-го по порядку простого числа $p_n.$

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

Также в Python есть функция is_prime(), которая может определять, является ли число простым. Но перебирать ряд натуральных, пользуясь этой функцией, - тоже выходит слишком медленно.

Поэтому, знающие люди, подскажите, пожалуйста, более быстрые реализации, а еще лучше формулу для $n$-го простого числа, чтобы его можно было вычислять моментально, а не развертывать вот эту всю бессмыслицу с переборами. На данный момент я пробую искать решение по stackoverflow, а также смотрю файлы, которые мне выдал учитель; как я понимаю, это кусочек документации Pythonа. Но ничего удовлетворительного это пока не дало.

[Евгений Машеров]

Увы, такой функции нет (и, возможно, в принципе нет, если не считать реализации со списком П.Ч. и поиском по нему). Есть критерии (тесты) простоты, но они либо носят вероятностный характер, либо требуют очень большой затраты вычресурса (наподобие проверки по всем простым вплоть до корня из N), либо применимы только к числам специального класса.
Возможно, если бы Вы уточнили проблему, можно было бы дать более конкретный совет. А пока только скажем, что если нужно n-ное простое число, но ничего кроме как хранить массив и выбирать соответствующий элемент, предложить не можем. Но возможно, что для поставленной задачи сгодится и что-то иное, для чего реализация существует.

[qtrln]

Евгений Машеров в сообщении #1623745 писал(а):

Возможно, если бы Вы уточнили проблему, можно было бы дать более конкретный совет.

Проблема простая - найти точную сумму всех простых чисел в интервале от 2 до $10^9$ с двойкой включительно.

-- 25.12.2023, 08:15 --

Python может подсчитать сумму простых чисел до $10^8,$ далее программа зависает. Но, с другой стороны, и простых чисел с какого-то момента становится заметно реже. Сейчас надежный человек, мой однокашник, занимается тем, что в ручном порядке ищет простые числа в интервале $[10^8, 10^9].$ Он знает все признаки делимости и уже нашел парочку простых чисел.

[Евгений Машеров]

А не проще ли будет воспользоваться решетом Эратосфена? Если можно держать в памяти массив из миллиарда чисел (а ещё лучше из миллиарда бит), и можно его сократить вдвое (рассматривая только нечётные, изначальную двойку "держим в уме" и прибавляем потом), или ещё более. Если есть ограничения по памяти - возможно "сегментированное решето".

-- 25 дек 2023, 10:45 --

По-видимому, лучшее из известных формул для вычисления простых это
$\frac {p_n} n= \log n+\log\log n -1+\frac{\log\log n -2}{\log n}-\frac{(\log\log n)^2-6\log\log n+11}{2(\log n)^2}+o(\frac 1 {(\log n)^2)}$
Но она для Вашей задачи не годна, она асимптотическая.

Цитата:

Again considering the $2\cdot10^{17}$th prime number 8512677386048191063, this gives an estimate of 8512681315554715386; the first 5 digits match and relative error is about 0.00005%.

А Вам нужны точные значения.

[wrest]

qtrln в сообщении #1623750 писал(а):

Проблема простая - найти точную сумму всех простых чисел в интервале от 2 до $10^9$ с двойкой включительно.

Посмотрите вот тут: A007504

Для проверки, сумма первых $10^9$ простых чисел равна 11138479445180240497

[ShMaxG]

Формулы для вычисления произвольно простого числа известны, вот например: https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B2%D0%B0%D1%8F_%D1%84%D0%BE%D1%80%D0%BC%D1%83%D0%BB%D0%B0_%D0%92%D0%B8%D0%BB%D0%BB%D0%B0%D0%BD%D1%81%D0%B0 Встает, конечно, вопрос о том, насколько ее применение эффективно, но тем не менее.

[Geen]

qtrln в сообщении #1623738 писал(а):

а еще лучше формулу для $n$-го простого числа

Пожалуйста https://en.m.wikipedia.org/wiki/Formula_for_primes

qtrln в сообщении #1623738 писал(а):

чтобы его можно было вычислять моментально

Это смешно, да.

qtrln в сообщении #1623738 писал(а):

не развертывать вот эту всю бессмыслицу с переборами.

Именно в переборах весь смысл - иначе бы криптография не работала.

qtrln в сообщении #1623750 писал(а):

найти точную сумму всех простых чисел в интервале от 2 до $10^9$ с двойкой включительно.

Ничего лучше решета тут не будет - ведь нужно не одно простое число, а все.

[Евгений Машеров]

Да, и касательно того, что я заявляю "нет такой формулы", а тут приводят ссылки и даже на несколько. Моё утверждение состоит в том, что нет формулы, которая была бы пригодна для решения Вашей задачи. Все существующие - это "научно-спортивный результат", доказующий мощь человеческого ума, но непригодный для практического использования. Одна из формул представляет собой сумму экспоненциально возрастающего в зависимости от n числа слагаемых (а в каждом слагаемом немногим меньшая сумма в знаменателе), вторая выражает через решение системы 26 уравнений (немного - но это диофантовы уравнения, для которых надо узнать, имеют ли они положительное решение), третья выглядит необычайно просто, всего лишь возводим в некую степень некое число и вуаля - его целая часть и есть искомое, только вот основание степени никому неизвестно, а чтобы его вычислить, надо выписать все-все простые числа, есть ещё несколько подобных, и во всех фигурирует константа, которую надо задать с бесконечной точностью (и научиться работать с числами бесконечной точности).
Как бы я решал подобную задачу? Ну, для начала узнал бы, чем могу пользоваться. Например, если мне нужны простые числа вплоть до миллиарда - могу ли я задать массив из миллиарда элементов? А если числовой нельзя, то можно ли битовый? А если нельзя миллиард, то, может, полмиллиарда доступны?
Первое простое число, двойку, рассматривал бы особо, задав его начальным значением суммы, а массив обозначал бы простоту чисел (поэтому бита хватит - 1 - составное, 0 - если мы уже проверили участок массива, соответствующий данному числу, то 0 означает простое, если не проверили - то "неизвестно", инициализируется массив нулями). Первый элемент массива соответствует числу 3, второй 5 и т.п. нечётным числам. Идём по массиву, если очередное число m помечено 1, то пропускаем, если 0, то прибавляем его № к сумматору и затем отмечает все числа вида $km, k>1, km<N$ единицами (поправляя шлем лохагоса Προφανές - это не элементы массива $km$, так было бы, если бы не выбросили чётные и единицу в самом начале). То есть поймали грека Эратосфена и продали самим себе в рабство, решетом числа просеивать.
Если массив такого размера доступен - всё довольно быстро. Если максимальный размер меньше - придётся резать на куски и обрабатывать по частям, тут уже есть интересные алгоритмические задачи.