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.
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.
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.
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.
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.
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.
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.
There are really three separate questions considered in this thread:
Is some given number a prime?
How can you generate all the primes below some given number?
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.
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?
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.
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.)
I guess when people make that distinction they are using the word formula to mean a 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.
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. 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.
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.
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.
(Go ahead; implement Fermat prime-testing on the Fractran machine. 
)
Less trivially (and somewhat famously), the polynomial n² + n + 41 has a prime value for every whole number n < 40.