You may have heard of the Sieve of Eratosthenes, which is a way to find out what all the prime numbers are. A prime number is a number larger than 1 that cannot be divided by anything but itself. Some examples are 2, 3, 5, 7, 11, and 13, but what others are there? In ancient times, Eratosthenes created a way to write down all the numbers, and then systematically cross out all that are not prime numbers. First, he crossed out all the ones that were multiples of 2, except for 2 itself. Then he crossed out all the multiples of 3, and then all the multiples of 5, because 4 was already crossed out for being a multiple of 2, so all multiples of 4 would already be crossed out. Then he crossed out all multiples of 7, and 11, and 13, and whichever numbers never got crossed out were primes by definition.
Now, I want to apply this same technique to list all the semi-primes. These are numbers that are the product of two primes, and therefore they are the next most complicated numbers after the primes. They only factorize into a product of themselves and 1, or the product of two primes in the middle. There are two kinds. The first kind are the squares of primes, where the two prime factors are the same number. The second kind are not squares, and they are two different numbers multiplied together. Here is how to use the Sieve of Eratosthenes to weed them out from the rest.
First, write out all the numbers in a chart, with each row being twelve wide, because that will be very convenient later. Next, for convenience, start the chart at 13, so that the first row goes from 13 to 24, and the next goes from 25 to 36, and so on. This will avoid any strange exceptions for very small numbers, and anyone can probably figure out all the semi-primes less than thirteen just by trial and error. First, we will perform the typical Sieve of Eratosthenes to find out which ones are composite or prime, because semi-primes can only fall into the composite category. Instead of crossing them off, we will instead color them a different color, say, green, because we will need to keep using them later. This is the first place where using 12 as the row length is handy. All we have to do to mark all the multiples of 2 and 3 are to color several entire columns green, so that they are definitely composite just from where they are on the table. We need to color the columns starting at 14, 16, 18, 20, 22, and 24 green for being divisible by 2, and we need to color 15 and 21 green for being divisible by 3. Now we know that primes can only occur in the columns that start with 13, 17, 19, and 23, and semi-primes can occur only in the eight others.
Now here is the next part where twelve comes in handy. The columns starting at 16, 20, and 24 all contain numbers that are divisible by 4, which guarantees 2 prime factors, plus however many factors are also in the number, making it definitely not a semi-prime. This is the property of semi-primes that is crucial to this Sieve working: any multiple of a semi-prime is automatically not a semi-prime, just like any multiple of a prime is automatically not a prime. So because three columns are definitely not semi-primes, we will color them all another color, say, red, to denote this. Also, the column that starts with 18 contains numbers that are all divisible by 6, which results in none of them being semi-primes for the same reasons as the other columns that start with 16, 20, and 24. So now we have a lovely pattern: 4 columns that are colored red and contain to semi-primes at all, 4 that are colored green and contain lots of the semi-primes, and 4 that are colored, say, white, which contain all the prime numbers. However, this is not our final answer, because numbers are far more complex than this. In fact, there are many numbers in the green "semi-prime" columns that are not semi-prime, and many semi-primes or even non-semi-primes with more that two prime factors, in the white "prime" columns. Note that the red columns definitely contain no primes or semi-primes whatsoever, and the green columns definitely contain no primes whatsoever, because of the rules of multiples of primes and semi-primes.
Now, let's start getting interesting. We have so far only crossed off the multiples of 2 and 3 and colored them green for composites, or "possibly semi-primes," but we need to also cross off multiples of 5 and 7. These are more complicated because they are not in columns. The fives go like this: start in the 15 and 20 columns with the numbers 15 and 20, and then start going downward diagonally, and for each row you go down, go over two columns to the left. Also, when you run off the left edge or are about to, start over at the right edge on the same row with a new multiple of 5. Whenever this process lands you on a white number, color it green. The same thing goes for 7, but you start on 14 and 21, and you go over two spaces to the right every time you go down a row. Next, for 11, it is actually much simpler. You start at 22, and you go diagonally down and to the left, one down for every left. When you reach the edge, you jump to the end of that row and you start again. For 13, it is similar, but you start at 13, the very uppermost left hand number on the table, and you go diagonally down and to the right. When you reach the end, skip an entire row and then start at the left hand side of the row below that. Those are the simple, or slightly complicated, rules for 5, 7, 11, and 13. The other prime numbers have similar diagonal rules, where you jump over sideways for every row or rows you go down. Fortunately, they are on the whole, simpler than 5, 7, and 11, because they will only ever have one multiple per row of the chart, because a row is twelve long, and "down one row" is the same as "plus 12." 17 goes one row down, and five to the right. 19 goes one row down and seven to the right, or two rows down and five to the left. These can all be figured out by using modular arithmetic.
Now that all the composite numbers have been colored green, it is time to color all the multiples of semi-primes blue, to mark them as definitely not semi-primes. We have already done 4 and 6, so first we must do multiples of 9. We start on 18, and we go down and three to the left, and we also skip 9 spaces forward, to the right, when we reach somewhere close to the left side of the chart. Note that all the squares we land on will already be marked green for being multiples of 3, so we need to color them red over the green by changing the color entirely. Next, we do 10. This is similar to 5, but we only start on 20, and we still go two to the left for every row. In fact, when we did the fives in the Sieve of Eratosthenes on our number chart, we could have just counted all the multiples of five starting at 15 and skipping forward one row and back two spaces, because all the others would be multiples of 10 and therefore could be colored red right from the start for being a multiple of a semi-prime. Next, we do 14, because it is the first number of our chart that is not colored white still, or colored red, so it must be a semi-prime. 14 goes like this: we start at 14, and we go down one row and over 2 spaces to the right. Note that the first number for which this actually changes something because none of the other numbers caused it to be colored red, is the number 98, because every multiple of 14 smaller than that is also a multiple of a smaller semi-prime, and it takes until the semi-prime is multiplied by the larger factor, in this case 14 times 7, in order for a multiple of 14 to be colored red that isn't already. This is like how for primes, anything less than the prime's square will have been caught by being a multiple of a smaller prime. This observation is rather important in figuring out how long it will take before all the semi-primes and primes below a certain limit are determined.
Next, we do 15, which is the same, except we start at 15 and we go over three spaces for every row we go down. The first number we actually catch this way is 75, which is 15 times its largest factor, 5. This is smaller than the one that 14 caught, because the factors of 15 are tighter together, so the first number it is able to catch on its own will be a bit smaller than that of 14, because the largest factor of 15 is smaller than the largest factor of 14. This is another interesting observation of our process so far. Next, we need to jump forward all the way to 21, which gives us its first new non-semi-prime once we reach the number 21 times 7, which is 147. From there it is down two rows and over three to the left, or down one and over nine to the right, coloring any number we land on red, that isn't already red, of course, but instead is green, because it is definitely already a composite number, and hence, green. Next is 22, because it is a semi-prime as well. The first new red-colored number it gives us is 242, and from then onward it is down two rows and over two spaces to the left, or down one and over ten to the right. From here on out, it gets very predictable, with each semi-prime having its own diagonal rule on how to find the next multiple on the number chart, just like the primes did. And now, because all the numbers are bigger than twelve, there will never be more than one of them on a single row, although there will now be quite large amounts of rows with none at all on them, meaning that we will have to go down multiple rows in order to get to the next multiple of this number.
That is it. That is how to use the Sieve of Eratosthenes to weed out the semi-primes as well as the primes. And you will notice from the finished chart that there can only ever be three semi-primes in a row if they are either just above or just below a multiple of twelve, and there can never be any four semi-primes in a row, because of the fact that the fourth one will always be divisible by 4 and hence not a semi-prime. This can be easily seen by looking at the rows and columns and seeing which columns are colored red, meaning that no semi-primes can ever occur there. But how do we know when to stop? For the original Sieve of Eratosthenes, we can stop once we reach the square root of the total number of numbers for which we want to apply the Sieve, because of the way in which new composite numbers are caught. In a similar way, we want to stop the new Sieve of Eratosthenes at around the square of the cube root of the total number, due to how new numbers that are not semi-primes are caught be the algorithm, so that the smallest new non-semi-prime that can be caught is approximately the square of the cube root, multiplied by its largest factor, which we will assume is the cube root, or the square root of the square of the cube root. The product gives us the total number of numbers that we want to subject to the Sieve, meaning we caught every one of them less than our preset maximum value. Alternatively, we could have assumed that the largest factor was half of the square of the cube root, which would have given us a product of the square of the square of the cube root, all of that then divided by 2, which is definitely bigger than our entire preset limiting value. So in conclusion, a good idea is to stop with the multiples of semi-primes once the semi-primes you are using to further apply the Sieve algorithm start to get as big or bigger than the square of the cube root of your total amount of numbers to which you want to apply the Sieve, or more exactly, the biggest number to which you want to apply the Sieve, because the numbers 1 through 12 are left out at the beginning. And that is how to find out what all the semi-primes are below a certain value.
Comments