This Idea will work perfectly, but it can be so unwieldy that it qualifies as half-baked.
When wanting to generate a list of prime numbers (which are only perfectly divisible by themselves and One), you start by creating a "candidate", which you then apply various tests to determine whether or not
it is prime.
The simplest way of obtaining a candidate is simply to add One to the last candidate: If I started at 2, then the next candidates are 3, 4, 5, 6, etc.
However, this is wasteful because we know that all the even numbers are divisible by 2, so why waste time generating those-as-candidates (not to mention testing them for primality)? So we begin at 3 and add 2: 5, 7, 9, 11, 13, etc.
But wait! Every third number on this list is perfectly divisible by 3! Why generate/test them, if we can prevent it? So, now we can introduce the algorithm and Table that make up this Idea. Below, the Table is an array of numbers, accessed by variable T[].
Start with the variables X, Y, and Z. Let X be initialized as Zero, and we will increment it by One at the end of the following loop (each pass of which will create one Candidate, variable C from a special Multiplier, M).
Let Z be the quantity of numbers in the Table. Now the algorithm is basically this:
'remember to DIMension the variables and initialize M, Z, and the T[] array!
10 X = 0 'QBASIC code
20 FOR Y = 1 TO Z
30 . C = X + T[Y]
'test Candidate for primality
40 NEXT Y
50 X = X + M
60 IF X < {pick end point} THEN
70 . GOTO 20
80 END IF
Please ignore the periods above, which are only being used for indenting. I have deliberately left the above a little vague, to be able to show how it works in different scenarios.
Consider the FIRST scenario at the start of this Idea. In this case, M is initialized to 1, Z is 1, and T[] therefore has a single entry, which is 1.
On the first loop-by of Line 30, C is 0 + 1, or 1
Code-flow exits the FOR loop,
adds M to X (which becomes 1), and hits the GOTO, so on the next loop-by of Line 30, C is * 1 + 1, or 2
The next loop-bys will yield 3, 4, 5, etc, just as described in the first scenario.
In the second scenario, M is 2, Z, is 1, and the Table again holds the single value of 1. On the first loop-by at Line 30:
C = 0 + 1, or 1
As before, X has M added to it (becoming 2), and the GOTO quickly brings us back to Line 30:
C = 2 + 1, or 3
And you can see that the series of odd numbers will continue to be generated. Note that the Prime number 2 is NOT produced by the algorithm -- but this is because 2 is incorporated into M.
The special multiplier M will always be the product of all the Prime numbers that we are working with, in a particular Scenario. SO, in the Third Scenario, M is 2*3 or 6, and Z is 2, and Table T[] holds the values of 1 and 5. Thus the first time we get to Line 30, C = 0 + 1, or 1 -- and because this time Z is 2, we quickly loop to get the second table item: C = 0 + 5, or 5.
Then code-flow adds M to X (which becomes 6) and bounces off the GOTO, and back at Line 30 we have:
C = 6 + 1, or 7, and (next T value) C = 6 + 5, or 11.
Then codeflow again adds M to X (which becomes 12) and bounces off the GOTO, and back at Line 30:
C = 12 + 1, or 13, and C = 12 + 5, or 17.
People who play with prime numbers will undoubtedly notice the similiarity to a very well-known fact, that every prime greater than 3 has the form 6X+1 or 6X-1 (where X is 1 or more). The ONLY reason I'm doing it this way is because this way can be extended!
In the next scenario, we can prevent any Candidates which are perfectly divisible by 5. M is 2*3*5 or 30, and Z is 8, and T[] holds the values of 1, 7, 11, 13, 17, 19, 23, and 29. To see why, start by reconsidering that Third Scenario in terms of 6X+1 and 6X-1:
01 03 05
07 09 11
13 15 17
19 21 23
25 27 29
31 33 35
These are the odd numbers produced by the Second Scenario. Every number in the middle column is divisible by 3, so by deleting it, its first values (less than 6) give us the values used in the Third Scenario Table -- and modifying it just a bit:
. 01
05 07
11 13
17 19
23 25
29 31
35
Note that the numbers that would naturally fit in-between each of the above pairs is a multiple of 6 (6, 12, 18, etc). Thus do all Primes (and Prime Candidates) greater than 3 have the form of either (6 * X) + 1 or 6X-1.
NOW consider this arrangement, of those Candidates produced in the Third Scenario:
01 07 13 19 25
05 11 17 23 29 (next number 30)
31 37 43 49 55
35 41 47 53 59 (next number 60)
61 67 73 79 85
65 71 77 83 89 (next number 90)
By inspection, you can see that each group of ten numbers has at its lower-left and upper-right corners, values which are perfectly divisible by 5. Now that we see the pattern, they can be eliminated -- leaving us with eight values for the Table, and M=30, for the Fourth Scenario of this Algorithm.
For the Fifth Scenario, we take the above pattern of numbers, and extend it to 210, which happens to be 2*3*5*7, and which will be M here. Then find all the values in that list which are divisible by 7, and remove them. ALL the others (48 of them, I think) will be the list that goes in the Table, and set Z appropriately.
Note that this Agorithm does not get any more complex, no matter what Scenario is tried. It is as easy to generate Candidates using the Third Scenario as it is for the Fifteenth. Only the Table grows, exhorbitantly. (By the time M includes all primes up to 19, the Table will likely include more than a million numbers.) Still, the goal of reducing the total number of generated Candidates is indeed met by this Algorithm. In that M=2*3*5*7*11*13*17*19 Scenario, for example, NO values that are exactly divisible by any of those numbers will be generated as a Candidate, to be tested for Primality.