# Prime number generator
**URL:** https://boards.straightdope.com/t/prime-number-generator/736573
**Category:** Factual Questions
**Created:** [November 4, 2015, 12:39am UTC](https://boards.straightdope.com/t/prime-number-generator/736573 "2015-11-04T00:39:15Z")
**Posts on this page:** 20
**Page:** 1
### Author:  [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)
#### Post date: [November 4, 2015, 12:39am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/1 "2015-11-04T00:39:15Z")
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?
---
### Author:  [@leahcim](https://boards.straightdope.com/u/leahcim)
#### Post date: [November 4, 2015, 12:47am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/2 "2015-11-04T00:47:46Z")
> [@Enola\_Straight](#):
>
> 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 :()
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.
---
### Author:  [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)
#### Post date: [November 4, 2015, 12:53am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/3 "2015-11-04T00:53:46Z")
> [@Enola\_Straight](#):
>
> Can these two facts be combined in a formula to weed out non-primes?
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?
---
### Author:  [@Napier](https://boards.straightdope.com/u/Napier)
#### Post date: [November 4, 2015, 2:41am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/4 "2015-11-04T02:41:24Z")
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.
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [November 4, 2015, 2:43am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/5 "2015-11-04T02:43:43Z")
> [@Exapno\_Mapcase](#):
>
> However, no known formula or set of formulas can produce all primes. Many formulas can produce some primes.
If RH is true, then I wonder if there is a formula to produce all primes.
---
### Author:  [@Exapno\_Mapcase](https://boards.straightdope.com/u/Exapno_Mapcase)
#### Post date: [November 4, 2015, 4:18am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/6 "2015-11-04T04:18:25Z")
> [@Saint\_Cad](#):
>
> 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](http://math.stackexchange.com/questions/69628/riemann-hypothesis-and-prime-number-distribution).
---
### Author:  [@Saint\_Cad](https://boards.straightdope.com/u/Saint_Cad)
#### Post date: [November 4, 2015, 4:20am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/7 "2015-11-04T04:20:24Z")
> [@Exapno\_Mapcase](#):
>
> If you mean the Riemann Hypothesis then read [this page](http://math.stackexchange.com/questions/69628/riemann-hypothesis-and-prime-number-distribution).
And that page answers my question how?
---
### Author:  [@TriPolar](https://boards.straightdope.com/u/TriPolar)
#### Post date: [November 4, 2015, 4:34am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/8 "2015-11-04T04:34:05Z")
> [@Saint\_Cad](#):
>
> If RH is true, then I wonder if there is a formula to produce all primes.
That’s easy. The hard problem is a formula that produces all the primes without producing any non-primes.
---
### Author:  [@septimus](https://boards.straightdope.com/u/septimus)
#### Post date: [November 4, 2015, 7:37am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/9 "2015-11-04T07:37:11Z")
[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.](https://en.wikipedia.org/wiki/FRACTRAN)
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.
---
### Author:  [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)
#### Post date: [November 4, 2015, 9:10am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/10 "2015-11-04T09:10:19Z")
> [@Enola\_Straight](#):
>
> 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 :()
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.
---
### Author:  [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)
#### Post date: [November 4, 2015, 1:45pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/11 "2015-11-04T13:45:18Z")
> [@Enola\_Straight](#):
>
> Can these two facts be combined in a formula to weed out non-primes?
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!
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [November 4, 2015, 2:25pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/12 "2015-11-04T14:25:49Z")
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.
---
### Author:  [@Leo\_Bloom](https://boards.straightdope.com/u/Leo_Bloom)
#### Post date: [November 4, 2015, 2:36pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/13 "2015-11-04T14:36:38Z")
> [@Chronos](#):
>
> 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).
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [November 4, 2015, 4:41pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/14 "2015-11-04T16:41:24Z")
Yeah, I guess it does sort of look like that, in retrospect.
---
### Author:  [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)
#### Post date: [November 4, 2015, 7:23pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/15 "2015-11-04T19:23:47Z")
Leo’s lament puts me in the mind of this classic:
> [@Tom Lehrer as New Math](#):
>
> …
> _You can’t take three from two,
> Two is less than three,
> So you look at the four in the tens place.
> Now that’s really four tens,
> So you make it three tens,
> Regroup, and you change a ten to ten ones,
> And you add them to the two and get twelve,
> And you take away three, that’s nine._
> …
🙂
---
### Author:  [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)
#### Post date: [November 4, 2015, 7:31pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/16 "2015-11-04T19:31:08Z")
So, to turn **Chronos** ’ description into pseudocode (and thereby rob it of its poetic charm, I’m afraid):
```auto
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]
---
### Author:  [@Boyo\_Jim](https://boards.straightdope.com/u/Boyo_Jim)
#### Post date: [November 4, 2015, 7:44pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/17 "2015-11-04T19:44:29Z")
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.
---
### Author:  [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)
#### Post date: [November 4, 2015, 7:52pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/18 "2015-11-04T19:52:48Z")
> [@Boyo\_Jim](#):
>
> 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:
```auto
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…
---
### Author:  [@Boyo\_Jim](https://boards.straightdope.com/u/Boyo_Jim)
#### Post date: [November 4, 2015, 7:54pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/19 "2015-11-04T19:54:52Z")
I didn’t say I was a \*good \*programmer. 😛
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [November 4, 2015, 9:26pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/20 "2015-11-04T21:26:14Z")
> [@](#):
>
> 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.
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).
[Next page](https://boards.straightdope.com/t/prime-number-generator/736573.md?page=2)