Two relevant facts about primes:
Except for 2 and 3, all primes are of the form 6x-1 or 6x+1.
Except for 2 and 3, all squares of primes are of the form 12x+1. (a fact I learned on these boards…yet cannot find anywhere on the net :()
Can these two facts be combined in a formula to weed out non-primes?
These two facts are not unrelated. If we have a prime (or any number, really) of the form p = 6x-1, then p^2 = 36x^2-12x +1 = 12(3x^2 - x) + 1 = 12u+1 for u = 3x^2 - x.
Similarly if we have a prime of the form p = 6x+1, then p^2 = 12u+1 for u = 3x^2 + x.
So the second fact does not place a stronger restriction on primes than the first.
I’m not clear about your question. Obviously they can weed out some non-primes just by existing.
However, no known formula or set of formulas can produce all primes. Many formulas can produce some primes.
What would you expect those formulas to do?
By “formula” could you mean a deterministic black box that tries successively larger integers for division by all the integers smaller than their square root, and spits them out, or returns the nth one when you enter n? If your “formula” can do simple conditionals and iterating and the like, that would be a formula that can produce all primes.
I guess I’m asking about the definition of “formula”, but it seems like it’d be kind of hamstringing mathematics to define it such that this obviously feasible black box isn’t included in the definition.
If RH is true, then I wonder if there is a formula to produce all primes.
If you mean the Riemann Hypothesis then read this page.
And that page answers my question how?
That’s easy. The hard problem is a formula that produces all the primes without producing any non-primes.
[hijack from the trivia desk]
One way to generate all the prime numbers is to run the following program in John Conway’s FRACTRAN programming language.
17/91 ; 78/85 ; 19/51 ; 23/38 ; 29/33 ; 77/29 ; 95/23 ; 77/19 ; 1/17 ; 11/13 ; 13/11 ; 15/14 ; 15/2 ; 55/1
Starting with 2 in the Fractran machine’s only register, the powers-of-two 2[sup]2[/sup], 2[sup]3[/sup], 2[sup]5[/sup], 2[sup]7[/sup], 2[sup]11[/sup], 2[sup]13[/sup], 2[sup]17[/sup], 2[sup]19[/sup], 2[sup]23[/sup], … are generated in order. It’s a ridiculously slow way to generate the primes but it seems impressive that Conway could come up with such a brief prime-generation program in his peculiar Fractran language.
These facts are just instances of the following:
A number is neither divisible by 2 nor by 3 just in case it is of the form 6x - 1 or 6x + 1; also, this happens just in case its square is of the form 12x + 1.
These in turn are instances of the following:
A number is neither divisible by n1, nor n2, nor n3, …, just in case its remainder modulo the least common multiple of (n1, n2, n3, …) is also divisible by none of them. From this list of possible remainders for the number itself, we can also construct analogously a list of possible remainders for the number’s square.
These are rather trivial observations, and not of any great boon in enumerating primes or checking for primality.
You mean like this?:
Weed out all even numbers (except two). Weed out all numbers divisible by three (except three).
Keep going like that, and you’ve discovered the Sieve of Eratosthenes!
Just to continue the pattern a bit further, to make it clear:
Don’t even look at 4-- You’ve already weeded it out as divisible by two.
Weed out all numbers divisible by 5 (except 5)
Don’t look at 6-- Already weeded out
Weed out all numbers divisible by 7 (except 7)
8, 9, and 10 are already weeded out
Weed out all numbers divisible by 11 (except 11)
and so on.
Rats. I honestly thought Chronos was going to quote some geeky light verse (and wondered how he’d get the first line to scan).
Yeah, I guess it does sort of look like that, in retrospect.
Leo’s lament puts me in the mind of this classic:
So, to turn Chronos’ description into pseudocode (and thereby rob it of its poetic charm, I’m afraid):
Create array A consisting of elements A[2] to A[n].
Initialize all elements of A to TRUE initially.
For each *i* from 2 to *n*:
If A[*i*] is TRUE:
For each *k* where *k* is a multiple of *i* and *i < k <= n*:
A[*k*] := FALSE
Afterwards, all the elements of A which are still TRUE, are prime numbers.
This is the basic Sieve of Eratosthenes, and it’s quite efficient. There are still a few optimizations possible, however:
[ul]
[li]In the outer loop, you actually only need to go up to the square root of n. Any non-prime numbers above sqrt(n) will have been sieved out at that point.[/li][li]For the inner loop, you can start sieving at i squared rather than at the first multiple of i greater than i itself. That’s because any number between i and i squared must be either prime or a multiple of a number below i.[/li][li]And finally we can apply the optimization which the OP started the thread with: there’s no point in wasting space in array A on numbers which are a multiple of 2 or 3, since all of those will never be prime anyway. So you can rewrite the algorithm so that only numbers of the form (x * 6 +/- 1) are ever considered.[/li][/ul]
I wrote a program in BASIC to find primes. It worked, but it took like an hour to test the first couple of hundred integers. It would have eventually broken when the numbers got too big, but I lost patience with it long before then.
With the Sieve of Eratosthenes I would expect you could find the first couple of hundred integers in a matter of seconds, even in BASIC on a Commodore 64.
Of course, if you use this algorithm:
for *i* from 2 to *n*:
*prime* = TRUE
for *x* from 2 to *i - 1*:
if *i* is dividable by *x*:
*prime* = FALSE
if *prime* is TRUE:
print *i* + " is a prime number!"
… then it can take a while even on a fast modern PC…
I didn’t say I was a *good *programmer. 
Of course, you can take this a step further, too, and only include numbers in the array that aren’t multiples of 2, 3, or 5. Or 2, 3, 5, and 7, and so on. Or, of course, you could just exclude the even numbers, for two-thirds of the benefit of the 6n±1 method. It all depends on how much you value speed of the program vs. complexity (which usually translates to time spent programming).