## 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: