2 3 5 7 11 ... ?

[jursla.livejournal.com]

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

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

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

Comments

[pyka-npu3paka.livejournal.com]

вроде любой перебор по времени занимает больше чем решение по алгоритму, не?)

[salvator-vals.livejournal.com]

Зависит от алгоритма. Вдруг кто-нибудь откроет полиномиальный алгоритм с временем работы n^100^100^100. Теоретически он эффективнее прямого перебора, но для всех практических значений n перебор гораздо быстрее.