Login | Register
Nerd ParadiseArtisanal tutorials since 1999

The Pen-and-Paperless version!


The following is roughly my thought processes when I try to check to see if a number is prime in my head.

Is the number even?
Then it's not prime. Unless it's 2.

Does the number end in 5 or 0?
Then it's not prime. Unless it's 5.

If a number has a prime factor, then it has to be less than or equal to the square root of the number. It is impossible for a number to factor to two other numbers that are both greater than the square root, otherwise their product would be greater than the original number. That means you only have to check prime factors up to the square root of the original number. If you can't find any, then you can safely say the number is prime.

You also only have to check prime numbers up to the square root. All other numbers can be ignored because any factor can be expressed as a product of prime factors. It is pointless to check to see if a number is divisible by 21 when checking for primeness, because 3 is a factor of 21 and divisibility by 3 is easier to check for.

When you're checking to see if a particular factor, x, divides evenly into n and the primeness of n is the only thing you care about, then you don't have to worry about how many times x divides into n. This means you can add or subtract multiples of x to n to make checking easier. For example, let's say we want to check to see if 3575 is divisible by 7.

3575 / 7 = fraction or whole number?

70 is a factor of 7, so let's subtract 70 to make things easier

3505 / 7 = fraction or whole number?

The end result here will still be the same. Let's keep simplifying. 35 is a multiple of 7 which means 3500 is also a multiple of 7. Subtract 3500

5 / 7 = fraction or whole number?

Now the answer is obvious. 7 does not divide 3575. We can now continue checking other prime factors to see if 3579 is a prime.

Also, dividing a secondary number by another arbitrary factor, such as n after you've subtracted several factors of x out of it, will not change its divisiblness by x. For example, if we want to check to see if 49739 is divisible by 13, then we can subtract 39 (13 * 3) and be left with 49700, which, if is divisible by 13 means 49739 is also divisible by 13. We can divide 49700 by 100. If 49700 had a factor of 13, then dividing by 100 will not change this. 497 is much easier to work with than 49739.

Let's try some examples:

251

Check for divisibility by 3: 51 is a multiple of 3 so subtract that out. We're left with 200 which factors to 2 * 10 * 10 which doesn't have a 3 in any further factorization. Move on to 7. Subtract 210 from 251 because that's a multiple of 7. We're left with 41 which itself is prime so we move on to 11. 5 is not the sum of 2 and 1 (see divisibility rules for 11 and 3 digit numbers) so this is not divisible by 11. We move on to 13. We subtract 260 which is a multiple of 13 (13 * 20) and we're left with -9 which is not divisible by 13. The next number to check for is 17, but 17 square is 289 which is larger than 251 so 251 is prime.

197

Check for divisibility by 3: The sum of the digits are not divisible by 3 (see divisibility rules for 3) so this is not divisible by 3. It doesn't end in a 5 so it isn't divisible by 5. To check for divisibility by 7, then we can subtract 7 and not change its divisiblness-by-7. That leaves us with 190, which is divisible by 10 and 19, neither of which contain a factor of 7. The next prime number to check is 11. If we subtract 11*10, then we're left with 87. Since 88 is the well-known multiple of 11, then we know 87 isn't divisible by 11. We now check 197 for divisibility by 13. We add 13 to 197 and get 210 which divides into 21 and 10. 21 divides into 3 and 7. No 13's here. 14 squared is 196 so we don't have to check anything above 14. We've exhausted all possible primes so we now know 197 is prime.