Hacker News Reader

Parent Full thread

schoen

It also stops generating primes for n=40. See

https://en.wikipedia.org/wiki/Formula_for_primes#Prime_formu...

View on HN

It never stops generating primes, but it doesn't give a prime for every n.

Then why is it better than just

n

which also doesn't give a prime for any n, but does generate them all.

Because it grows exponentially. ( And it is interesting )

In reality you will use a O( (log n)^6 ) algorithm.

I think n² grows quadratically rather than exponentially.

::blush::

Nobody in their right mind uses AKS for primality testing. You use Miller-Rabin with an appropriate constant number of iterations, with complexity (log n)^(2 + o(1)). Or if you want provability, you use some fast variant of ECPP with (log n)^(4 + o(1)) complexity.

Reply on news.ycombinator.com