4 ms·
There is such a formula, it is very simple n^2+n+41 It doesn't generate sequential primes. That doesn't really matter, checking if a number is prime can be
by readerrrr 12y ago
There is such a formula, it is very simple
n^2+n+41
It doesn't generate sequential primes.
That doesn't really matter, checking if a number is prime can be done in sublinear time complexity. The real problem is factoring large numbers.
- schoen 12y agoIt also stops generating primes for n=40. See https://en.wikipedia.org/wiki/Formula_for_primes#Prime_formulas_and_polynomial_functions https://en.wikipedia.org/wiki/Formula_for_primes#Prime_formu...
- readerrrr 12y agoIt never stops generating primes, but it doesn't give a prime for every n.
- alphaBetaGamma 12y agoThen why is it better than just n which also doesn't give a prime for any n, but does generate them all.
- readerrrr 12y agoBecause it grows exponentially. ( And it is interesting ) In reality you will use a O( (log n)^6 ) algorithm.
- schoen 12y agoI think n² grows quadratically rather than exponentially.
- readerrrr 12y ago::blush::
- pbsd 12y agoNobody 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.
- jessaustin 12y agoThis degrades pretty quickly, however. Only 581 of the first 1000 numbers generated by that formula are prime. 11 also works initially as a constant, but it degrades even more quickly than 41.