One very neat thing to know, you do not need to go further up in known primes than the number itself. This I think everyone realises. But here is another one : you only need to go up to the square root of a number. Why? If it has a prime factor higher than its square root, it would need to have one lower than its square root too. And by hypothesis, you have already eliminated those.
So, to prime test any number up to 100 or even 121, you need go no further than testing up to 11. To know 11 is prime, it suffices to know it is not a multiple of 2 and 3. Sure, it is not a multiple of 5 and 7 either, which you can test by Eratosthenes' sieve, but when you cross out the relevant multiples of 5 and 7, except these themselves, you will find they are already crossed out as multiples of 2 and 3.
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 2 | 3 | 5 | 6 | 7 | 9 | 11 | 13 | 15 | |||||
| 2 | 3 | 4 | 5 | 7 | 8 | 10 | 11 | 13 | 14 | ||||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 | 12 | 13 | 14 | ||
| 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 15 |
Surrounding multiples of 5 are 10 and 15, already struck out as such of 2 and 3, and surrounding multiples of 7 are 7 itself and 14 which was already struck out as a multiple of 2.
When it comes to prime testing for 11, no big deal if you want to use the sieve for 5 and 7 too first. But what about 1001 or 11111?
I guess it is handy if the prime factors you test for only go up to the square root and not the number itself.
Here is another thing which is handy : make sure to eliminate one digit for each test for one factor. Starting with 1001. We don't need to test for 2. Three has one low multiple ending in 1, namely 21, which will bring us to testing for 7 at the same time:
| 1 | 0 | 0 | 1 |
| - | 2 | 1 | |
| 9 | 8 |
We might be up to something, 98 is not a multiple of 3, but maybe of 7 ... yes, 91 + 7 = 98 and we can get into our heads at once that 91 = 7*13. What if we had tested for 91?
| 1 | 0 | 0 | 1 |
| - | 9 | 1 | |
| 9 | 1 |
Ah, so 1001 is 11*91 or 7*11*13.
Now for 11111. We'll have a few prime factors to test for .... as square root is just above 105, we'll go up to 103.
3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103
Let's start with 3*7=21, first for 3, then for 7.
| 1 | 1 | 1 | 1 | 1 |
| - | 2 | 1 | ||
| 1 | 1 | 0 | 9 | |
| For 3 | ||||
| 1 | 1 | 0 | 9 | |
| - | 9 | |||
| 1 | 1 | |||
| For 7 | ||||
| 1 | 1 | 0 | 9 | |
| - | 4 | 9 | ||
| 1 | 0 | 6 | ||
| - | 5 | 6 | ||
| 5 | ||||
No.
| 1 | 1 | 1 | 1 | 1 |
| - | 1 | 1 | ||
| 1 | 1 | 1 | ||
| - | 1 | 1 | ||
| 1 |
No. In fact, all even places of the digit 1 will be 11 or multiples of it, and therefore all even places of the digit 1 repeated except 11 are non-prime. All places that multiple by 3 times the digit 1 will be involving prime factors 3*37 (which is 111). So, for repeated 1-digits, only test if uneven and not divisible by 3.
How about 13, with 91 as first shot?
| 1 | 1 | 1 | 1 | 1 |
| - | 9 | 1 | ||
| 1 | 1 | 0 | 1 | |
| - | 9 | 1 | ||
| 1 | 0 | 1 |
No, and we can also eliminate 101:
I am not going through all of it, I already did that on paper and you can do that by yourself, and I might hint there are chances 11111 is a prime, but you can check for yourself and some funny "disappointments" show up along the way. Oh, one more : as with my eliminating 101, any time you come to another prime factor than you tested for in the remainder, eliminate that one too (113, eliminate the final 3 and you have also eliminated the initial 11). Unless it is involved in the part you were subtracting. The rule is, if (x+y) is divisible by z, either both or neither of x and y must be so too. So, everytime one is and one is not divisible by z, the whole of (x+y) is not divisible by z.
Hans Georg Lundahl
Bibliothèque Georges Pompidou
St. Lucian of Beauvais
and Companions, Martyrs
8.I.2020
PS, if you also read French, here is a lesson on geometry:
New blog on the kid : Leçon de géométrie
https://nov9blogg9.blogspot.com/2020/01/lecon-de-geometrie.html
No comments:
Post a Comment