2 3 5 7 11 ... ?

[jursla.livejournal.com]

Математика давно бьется над вычислением простых чисел. На данный момент формулы их нахождения нет и неизвестно существует ли она в принципе.

По сути нахождение простых чисел - это просто перебор всех с исключением заведомо непростых чисел и групп чисел.

Как изменился бы мир если бы вывели формулу безошибочного стопроцентного нахождения простых чисел? Типа f(1) = 2, f(2) =3, f(10) = 29... f(n) = Pn

Comments

[roquefort-tln.livejournal.com]

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

[blackyblack.livejournal.com]

Чем вам перебор множителей не формула определения простого числа? Тут вопрос не в существовании формулы или алгоритма, а в сложности этого алгоритма. Сложность решета Эратосфена: O(n log log n). А суть вашего вопроса, по всей видимости, в том, что было бы, если бы придумали алгоритм с константной сложностью.

[daxi.livejournal.com]

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

[pyka-npu3paka.livejournal.com]

а между тем формула алгоритм для расчета всех простых чисел на любом заданном интервале есть и гугл вам его покажет=)

[eterevsky.livejournal.com]

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

С точностью вычислить n-е простое число, не вычисляя предыдущие простые числа сейчас действительно невозможно. В то же время его можно оценить: n-е простое число находится в районе n*ln(n). Эту оценку можно сделать гораздо более точной. Если докажут гипотезу Римана (http://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D1%82%D0%B5%D0%B7%D0%B0_%D0%A0%D0%B8%D0%BC%D0%B0%D0%BD%D0%B0), то оценки будут ещё точнее.

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

[igor-eta.livejournal.com]

ВЫ бы тогда спросили


"Как изменился бы мир если бы НЕ вывели формулу безошибочного стопроцентного нахождения простых чисел? Типа f(1) = 2, f(2) =3, f(10) = 29... f(n) = Pn"