News for hackers. Stuff that matters.
Re:Prime number patterns by readerrrr on Tuesday November 11, 2014 @12:21PM (#8590955)
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.

Re:Prime number patterns by schoen on Tuesday November 11, 2014 @12:41PM (#8591078)
It also stops generating primes for n=40. See

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

Re:Prime number patterns by readerrrr on Tuesday November 11, 2014 @12:47PM (#8591118)
It never stops generating primes, but it doesn't give a prime for every n.
Re:Prime number patterns by alphaBetaGamma on Tuesday November 11, 2014 @12:55PM (#8591159)
Then why is it better than just

n

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

Re:Prime number patterns by readerrrr on Tuesday November 11, 2014 @12:57PM (#8591173)
Because it grows exponentially. ( And it is interesting )

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

Re:Prime number patterns by pbsd on Tuesday November 11, 2014 @01:22PM (#8591286)
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.
Re:Prime number patterns by schoen on Tuesday November 11, 2014 @01:16PM (#8591258)
I think n² grows quadratically rather than exponentially.
Re:Prime number patterns by readerrrr on Tuesday November 11, 2014 @01:20PM (#8591275)
::blush::
Re:Prime number patterns by jessaustin on Tuesday November 11, 2014 @01:08PM (#8591214)
This 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.