Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

"Also I think we have shown using a variant of Galois theory that there can not be a closed from solution for the nth prime."

I don't think this is correct. For one, it is not clear what "closed form" would mean in this context. I think a reasonable variant would be "is there a polynomial time algorithm that, given n, outputs the nth prime." While my guess would be that the answer is no, I am certain that this is not known (and probably far, far out of reach).



Anyone else wondering more details:

https://www.quora.com/Is-finding-prime-numbers-in-P-or-NP

Interestingly the Polymath4 project in/around 2009 attempted to find such a polynomial algorithm.


Note that finding "a k-digit prime" is not the same as finding "the kth prime." I don't have any strong feelings either way about whether the former would be possible in polynomial time or not, but I would be pretty shocked if the latter were.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: