You can't really check whether a number is prime, you can only check whether it divides by a prime number smaller than the square root of the original number and rule it out if it does. So it's a question of ruling out as many as possible as quickly as possible.
First, you rule out even numbers and numbers ending in 5 (apart from 2 and 5).
The next obvious/easy thing to do is to add the digits and see if they add up to 3, if they do, the number divides by three i.e. 291 = 2 + 9 + 1 = 12 (unless you start with 3, which itself is prime).
But I've watched another couple of maths videos on YouTube, and what they boil down to is that there is a better test that helps you rule out more numbers. The test is - divide the original number by thirty and just look at the remainder, or take "number mod 30" if you are using a scientific calculator.
If the remainder is not a prime number, the original number is not prime. If the remainder is prime (or ends in 1, even though the number 1 itself is officially not a prime number) and the original number is less than 300, there is a two-thirds chance the original number is prime. The chance of it being prime is slightly better than 50% for numbers up to 1,500. That percentage drifts downwards, the larger the number is. So if the original number was above 1,500, you might as well just assume it is not prime, even if the remainder is prime.
If the original number passes the second test and you want to improve your chances of getting it right, you have to do the long hard slog with divisibility tests, and check if it divides by 7, 11, 13...
I hope this comes in handy next time you are in a pub quiz. I can't think of many other uses for such trivia.
Sunday Funnies...
2 minutes ago
6 comments:
Mark,
your '3-test' can be extended to avoid any dividing.
If you sum the original integers, sum the integers in the result, and so on until you finish with a single digit. If that digit is 3, 6, 9, the original is not prime
VFTS, sure, that method will rule out all numbers that divide by 3. Does it exclude the same numbers as the mod 30 rule? Maybe it does and I wasted my time :-)
VFTS, having thought about it while doing something else, where my suggested method gives you a slight edge over "adding digits" is numbers where the remainder is a prime.
For example, 1003 = 990 + 13. This tells you it can't divide by 13, so when you are grinding it out, you don't need to check whether it divides by 13 (it divides by 19 as it happens).
Counter-example, 1,001 = 990 + 11. If you don't notice that 990 divides by 11, you've missed the point.
mod 30 rule. Hmm, not sure. I'm more than a bit rusty on number theory.
Well, 30 is 2*3*5. That suggests to me that there should be a 210 (2*3*5*7) rule which on the plus side gives even better odds but on the minus side requires you to memorise all the primes up to 209.
VFTS, mod 30 rule is not an official thing. I just cobbled it together.
D, correct. You could do mod 210, or mod 2,310.
Post a Comment