"all such formulas require either extremely accurate knowledge of some unknown constant, or effectively require knowledge of the primes ahead of time in order to use the formula."
He is writing about formulae that are known to produce the n-th prime p(n) on input n. There are other kinds of prime-generating formulae. Consider, for example, the formula described by Eric Rowland in a recent issue of the Journal of Integer Sequences. Rowland's sequence is defined by
a(n) = a(n-1) + gcd(n, a(n-1))
and a(1) = 7. He shows that the values taken on by a(n)-a(n-1) are always either one or prime. However, it is not known whether all primes are produced by this sequence, and I expect it not to be the case! Another approach is to consider the values taken on by a polynomial with integer coefficients and in several unknowns. There exist polynomials for which all the positive values are all prime and in fact there exist such polynomials for which all prime numbers are found among the positive values. These prime-generating polynomials (about which more in the MathWorld article cited below) are, however, not a particularly efficient way of generating prime numbers.
- Podcast of the 3 October 2008 edition of The Internet Economy on ClassicFM http://tinyurl.com/3m2gug
- Weisstein, Eric W. "Prime Formulas." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/PrimeFormulas.html
- Rowland, Eric S. "A Natural Prime-Generating Recurrence." Journal of Integer Sequences, Vol. 11 (2008), Article 08.2.8 http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html
- Weisstein, Eric W. "Prime-Generating Polynomial." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Prime-GeneratingPolynomial.html