# Prime number generator **URL:** \ **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:** 2
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 4, 2015, 9:30pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/21 "2015-11-04T21:30:08Z")
The first form in the OP is a mere starting point in a sieve algorithm to list all primes. Much more work goes into doing it efficiently. The second form is useless. To use it, presumably, one would work backwards taking square roots of 12x+1 numbers. And then what? The square root is not worth your while plus it’s a (small) time sink. Note: there are _formulas_ that produce only primes. (The classic Hardy & Wright _Number Theory_ book gives one.) But these are not remotely computationally efficient and in many cases, not even computable. What you want to look for is an _algorithm_. ---
**Author:** ![Dr.Strangelove](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/dr.strangelove/32/6613_2.png) [@Dr.Strangelove](https://boards.straightdope.com/u/Dr.Strangelove)\ **Post date:** [November 4, 2015, 10:11pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/22 "2015-11-04T22:11:03Z")
Another factor is the existence of _probabilistic_ primality tests. There are tests which will tell you if a particular number is prime (or composite) with probability less than 1.0. Usually, these tests can repeated until you have whatever confidence level you require. Of course you can never reach perfect confidence with these tests. One might therefore think they’re useless if you can’t really prove anything. However, a computer running a “perfect” primality test also has some finite probability of failing (cosmic ray hit or whatever) in a way that gives you the wrong answer. A certain high confidence level is therefore all you really need unless you’re using the test in a mathematical proof of some kind. ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [November 5, 2015, 3:18am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/23 "2015-11-05T03:18:56Z")
There are also more relatively efficient “perfect” (as long as you don’t get a cosmic ray or whatever) primality tests. They’re not nearly as quick as the probabilisitic ones, but still much quicker than the naive brute-force method of checking all potential factors. So you might do a few runs of a quick probabilistic test to sift out (almost) all the composites, and then finish off with a perfect test to verify. ---
**Author:** ![Enola\_Straight](https://avatars.discourse-cdn.com/v4/letter/e/dec6dc/32.png) [@Enola\_Straight](https://boards.straightdope.com/u/Enola_Straight)\ **Post date:** [November 5, 2015, 4:37am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/24 "2015-11-05T04:37:21Z")
> [@leahcim](#): > > These two facts are not unrelated. _That I didn’t know_☹ ---
**Author:** ![filmore](https://avatars.discourse-cdn.com/v4/letter/f/7993a0/32.png) [@filmore](https://boards.straightdope.com/u/filmore)\ **Post date:** [November 5, 2015, 5:00am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/25 "2015-11-05T05:00:24Z")
> [@septimus](#): > > [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. I didn’t follow the wiki link in how the primes were generated > [@](#): > > Starting with n=2, this FRACTRAN program generates the following sequence of integers: > > ``` > 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... > > ``` I see how those numbers are generated, but then it says: > [@](#): > > After 2, this sequence contains the following powers of 2: What does it mean by “After 2”? I’m not seeing how the 2^prime numbers are coming out of the '2, 15, 825… ’ sequence. ---
**Author:** ![Walton\_Firm](https://avatars.discourse-cdn.com/v4/letter/w/45deac/32.png) [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)\ **Post date:** [November 5, 2015, 7:02am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/26 "2015-11-05T07:02:13Z")
> [@Chronos](#): > > 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). It would definitely make it more complex but I doubt that it would actually improve the speed. Adding more state and conditional branches (or, Heaven forbid, division or modulo operations) to a piece of code generally makes it slower by a constant factor. If, in exchange for that, it allows you to improve the running time by a polynomial factor (e.g. from O(n) to O(sqrt(n)) or to O(log(n)) then it’s usually worth it. But in this case it won’t do that; the total number of iterations for the inner and outer loop remains pretty much the same. The biggest advantage would be that it reduces the memory footprint of the algorithm, which can make a big difference if you have a fast CPU but slow memory, especially if you don’t have enough RAM and need to start swapping to disc. But going above 3 will give only modest further decreases in array size as well. In practice, special-casing up to 6n±1 seems to be the sweet spot where it can actually be worth it. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 5, 2015, 7:18am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/27 "2015-11-05T07:18:56Z")
> [@](#): > > Starting with n=2, this FRACTRAN program generates the following sequence of integers: > > 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, … This sequence continues … 910, 170, 156, 132, 116, 308, 364, 68, 4, … 4 is a power-of-two and corresponds to the 1st prime, 2[sup]2[/sup]. The second prime (3, represented as 2[sup]3[/sup] = 8) shows up after the Conway machine cycles 69 times; 2[sup]5[/sup] after 280 cycles; and so on. > [@filmore](#): > > What does it mean by “After 2”? I’m not seeing how the 2^prime numbers are coming out of the '2, 15, 825… ’ sequence. They come out very slowly, since Conway’s program implements a very trivial sieve, and has to use low-level brute force just to implement simple arithmetic. The non-power-of-two numbers are just the intermediate results in these tedious additions and multiplications. The “beauty”, if any, in the program is that it can function at all! 🆒 (Go ahead; implement Fermat prime-testing on the Fractran machine. 😛 ) If anyone wants to implements a Fractran machine and test the prime-generation program, do NOT do the indicated arithmetic, just store exponent vectors. The Fractran register would exceed 119 billion before the prime 7 is found and 2[sup]64[/sup] before 13 is found. ---
**Author:** ![septimus](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/septimus/32/410_2.png) [@septimus](https://boards.straightdope.com/u/septimus)\ **Post date:** [November 5, 2015, 7:30am UTC](https://boards.straightdope.com/t/prime-number-generator/736573/28 "2015-11-05T07:30:12Z")
> [@Walton\_Firm](#): > > In practice, special-casing up to 6n±1 seems to be the sweet spot where it can actually be worth it. There are 8 possible primes in any 30 consecutive large numbers, compared with 10 if (30k+5) and (30k+25) are not excluded. Since 8 is the number of bits per byte and bytes are convenient, this leads to another “sweet spot” known to many programmers: The primes in the first 300,000 integers can thus be encoded into 10,000 bytes. Some (many?) old sieves start with such a table to allow quickish detection of all smallish primes. ---
**Author:** ![Hari\_Seldon](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/hari_seldon/32/5173_2.png) [@Hari\_Seldon](https://boards.straightdope.com/u/Hari_Seldon)\ **Post date:** [November 5, 2015, 9:36pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/29 "2015-11-05T21:36:31Z")
There are really three separate questions considered in this thread: 1. Is some given number a prime? 2. How can you generate all the primes below some given number? 3. How many primes are there below some given number? The Riemann hypothesis is relevant only to #3. As for number 2, you really cannot improve much on the sieve AFAIK. However when you have a prime, you can start sifting at its square since all non-sifted numbers below that square are prime (if N is composite the least divisor is at most the square root of N). As for the first question, there are some extremely efficient but very sophisticated algorithms that do work perfectly (in principle) as well as some very efficient probabilistic methods (based on the “converse” of Fermat’s little theorem. Of course the converse is false but then you refine it finer and finer until the probability of the given number being composite is vanishingly small.) Being a simple soul myself I once devised an algorithm that could be run on a programmable HP calculator for a number of no more than 10 digits (the display size of the calculator). It first tested for divisibility by all the primes \< 30 and then starting with d = 31 it test divisibility by d, then d + 6, d + 10, d + 12, d + 16, d + 18, d + 22, d + 26 and then looped around and started over with d = 61 and so on. It continued to the square root of the given number. The point is to avoid testing by multiples of 2, 3, or 5. Calculating all night the 1977 vintage computer informed me in the morning that the largest 10 digit prime was 9,999,999,967. So it must have been able to do in approzimately an hour. ---
**Author:** ![Walton\_Firm](https://avatars.discourse-cdn.com/v4/letter/w/45deac/32.png) [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)\ **Post date:** [November 5, 2015, 10:38pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/30 "2015-11-05T22:38:55Z")
> [@Hari\_Seldon](#): > > As for number 2, you really cannot improve much on the sieve AFAIK. However when you have a prime, you can start sifting at its square since all non-sifted numbers below that square are prime (if N is composite the least divisor is at most the square root of N). See the second one of the three optimizations I listed. 😉 ---
**Author:** ![filmore](https://avatars.discourse-cdn.com/v4/letter/f/7993a0/32.png) [@filmore](https://boards.straightdope.com/u/filmore)\ **Post date:** [November 6, 2015, 7:49pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/31 "2015-11-06T19:49:51Z")
Are there equations which generate just a subset of primes? That is, rather than trying to find something that generates all the primes, find something that just generates prime numbers even if it’s not all of them. For example, an equation which easily produces just a subset of prime numbers like 5, 17, 59… I’ve often wondered if the set of primes isn’t produced by a single formula. Rather, there are many subsets of primes and different formulas would produce different subsets. We have trouble seeing these subset formulas because we’re looking at all the primes and the subsets are hard to pick out. It would be as if an infinite number of different sine waves were graphed and we could only see where they intersected the X axis. Assume the sine waves were something unusual like sin((xpi)/5+x) or whatver which wouldn’t produce a regularly-shaped wave. The distribution of the dots might look random if lots of those weird sine waves were all graphed together. If we didn’t know what equations were generating the dots on the X axis, we would have a hard time figuring out how those X values were computed. But if we could see just the subset of values which were produced by one single sine wave, we could perhaps determine that a sine wave equation could be used and compute the rest of the values that particular sine wave would produce. Is there anyway to determine if that’s the case with the prime number distribution? Could there be many different equations where each equation produces a non trivial subset? ---
**Author:** ![Thudlow\_Boink](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/thudlow_boink/32/320_2.png) [@Thudlow\_Boink](https://boards.straightdope.com/u/Thudlow_Boink)\ **Post date:** [November 6, 2015, 8:23pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/32 "2015-11-06T20:23:23Z")
> [@filmore](#): > > Are there equations which generate just a subset of primes? There are certainly equations which generate _finite_ subsets of primes. For example, f(x) = 0x + 13 generates a prime number value for any x. 🙂 Less trivially (and somewhat famously), the polynomial n² + n + 41 has a prime value for every whole number n \< 40. ---
**Author:** ![Walton\_Firm](https://avatars.discourse-cdn.com/v4/letter/w/45deac/32.png) [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)\ **Post date:** [November 6, 2015, 9:44pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/33 "2015-11-06T21:44:27Z")
Also, this sequence: 31, 331, 3331, 33331, 333331, 3333331, 33333331, … (actually, the “…” is a lie) ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 7, 2015, 3:37pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/34 "2015-11-07T15:37:27Z")
> [@filmore](#): > > I’ve often wondered if the set of primes isn’t produced by a single formula. See my previous post. Formulas for the entire set of primes exist. They just aren’t useful. OTOH, algorithms for producing all primes in sequence using seive-based methods are reasonably fast, up to a point. The storage requirements get quite cumbersome after a bit. Eventually you start trading time for storage and then it gets slower and slower. As far as subsets of primes go, I once attended a lecture by the amazing John Conway where he gave and derived such a formula. It initially seemed like magic but turned out to be a sort of “gotcha” result. (At the start of the lecture, he presented several topics for the audience to choose from and went into the hallway. We voted on our favorites and this one won the most votes.) ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 7, 2015, 4:08pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/35 "2015-11-07T16:08:37Z")
What is the distinction being drawn between a “formula” and an “algorithm”? ---
**Author:** ![Walton\_Firm](https://avatars.discourse-cdn.com/v4/letter/w/45deac/32.png) [@Walton\_Firm](https://boards.straightdope.com/u/Walton_Firm)\ **Post date:** [November 7, 2015, 5:54pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/36 "2015-11-07T17:54:38Z")
> [@Indistinguishable](#): > > What is the distinction being drawn between a “formula” and an “algorithm”? I guess when people make that distinction they are using the word formula to mean a [closed-form expression](https://en.wikipedia.org/wiki/Closed-form_expression). Basically, something which can be computed in a finite number of operations which is independent of the input values. As opposed to an algorithm, which can contain things such as loops, recursion, extra storage space used for intermediate results, etc, and where in some cases it may be impossible to prove whether it will ever finish at all. ---
**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\ **Post date:** [November 8, 2015, 6:05pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/37 "2015-11-08T18:05:48Z")
> [@Indistinguishable](#): > > What is the distinction being drawn between a “formula” and an “algorithm”? A formula is … a formula. It has symbols, numbers, etc. E.g., _e_[sup]π[/sup] is a formula. But it frequently can’t be directly used to calculate the value. (If you’re thinking “Well, I can use Taylor series expansion plus Machin’s formula for π …” then you are stepping outside the formula as given into another domain.) An algorithm tells you _how_ to do something. Take [Chaitin’s\_constant](https://en.wikipedia.org/wiki/Chaitin%27s_constant). Nice little formula for it. Impossible to actually compute to any non-trivial number of bits. If we could, then a lot of open problems (like the Goldbach Conjecture) could be solved. And that’s just on the “edge” of non-computable. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 8, 2015, 9:20pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/38 "2015-11-08T21:20:54Z")
What symbols do we allow in a formula? What is the intrinsic value of a categorization which considers algorithms not to be formulas as well? ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [November 8, 2015, 9:30pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/39 "2015-11-08T21:30:53Z")
The formula vs. algorithm distinction was raised by an admitted non-expert. As such IMO he’d be looking for pretty much arm-waving distinctions along these lines: “Formula” ~= “something I was exposed to in HS or college bonehead algebra”. vs. “Algorithm” = “anything more complicated than that.” IMO having the real SD mathematicians (a set not including me) debate the distinction seems … perverse. It is amazing to me how many intelligent but not math-oriented people really want to believe there exists a simple algebraic function P(n) that for positive integer n returns the n[sup]th[/sup] prime using nothing but simple arithmetic operations in a trivial one-pass evaluation. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [November 8, 2015, 9:44pm UTC](https://boards.straightdope.com/t/prime-number-generator/736573/40 "2015-11-08T21:44:16Z")
Right, I should say, my point in mentioning the algorithm-formula distinction is really just befuddlement that actual proper mathematicians seem to be thinking of it as a distinction worth drawing (in some sense more subtle than, say, formulas are those algorithms which run fast) rather than dissolving. [Previous page](https://boards.straightdope.com/t/prime-number-generator/736573.md?page=1) [Next page](https://boards.straightdope.com/t/prime-number-generator/736573.md?page=3)