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.-- Vernon, Jun 22 2004 When my scrolling finger begins to cramp, I know who the author is. Definitely more of a novelist than a short story writer.-- normzone, Jun 22 2004 I thought this would be an idea to mathematically select the best elected officials.-- phoenix, Jun 22 2004 Only Vernon could write an epic on maths, and without the aid of formulae writing tools-- engineer1, Jun 22 2004 [Tabs], I could have written that in any of several computer languages. But the HalfBakery is visited by lots of people who don't know any, and BASIC was designed for beginners. For widest audience, what other choice is there? And as for the GOTO, I do know I could have avoided it by putting in another FOR loop. But the additional indenting would have been ugly, the way text gets presented here. Also, I wanted the termination-test near the end (again for the benefit of beginners), and GOTO is much more intuitively obvious than, say, a DO/WHILE loop (--which also would have meant more indenting!). I stand by my choices, and I sneer at the prejudice represented by any associated fishbone.
Next, this algorithm does have a lot of similarity to the Sieve of Erasthothenese, in the way it operates. Both are methods of preparing filters for numbers. However, the goal of the Sieve is to directly find primes. Here the goal is to find likely Candidates. In that last-described Scenario, involving 19 and the million-item Table, it happens that M will equal 9,699,690. I could set X in Line 10 to a nice large multiple (say 1000) of that value, run the algorithm, and get a million Candidates, each larger than 9 billion, that have been pre-weeded by those commonest prime-divisors.-- Vernon, Jun 22 2004 What's the invention here? I don't think 'a computer program to look for prime numbers' is really halfbakery worthy, nor slightly original.
// But wait! Every third number on this list is perfectly divisible by 3! //
You exclaim this stuff like you're the first human ever to notice. You're not.-- waugsqueke, Jun 23 2004 [Tabs], it depends on the programming environment. I started out with BASIC, and less than 4K of RAM to practice in. So, the more I wanted to do, the better I had to get (efficient code). Adding more RAM to that computer merely let me write bigger programs that STILL had to be squeezed to fit. I think that nobody who perseveres in such a programming environment is going to come out of it a lousy programmer. Not to mention that modern BASICs allow a programmer to learn structured program-organization, and so the use of GOTO can be reserved for where it more useful/valuable/efficient than any other programming keyword (like jumping from the middle of one deeply nested set of loops and/or tests, into the middle of another).
[waugsqueke], in the past I used the simple 6X+1 and 6X-1 to create Candidates for primality (OTHER tests discover that), but was bothered by not having a way to preweed other prime divisors than 2 and 3. The Idea here is the successful -- and generic! -- resolution of that problem. As for the exclamation marks, that was just literary license in action.-- Vernon, Jun 23 2004 random, halfbakery