How do you work out if a number is a prime number?

Answer 1

A number is prime if is has exactly two unique positive factors, the number 1 and itself.

E.g. 5, 7 and 11 are all prime numbers. The number 1 is not prime.

However, 15, for example, is not prime because 3 x 5 = 15, i.e. is has more than two factors.

In terms of working out whether or not a given number is prime is more difficult the larger the number.

• These steps may seem long and difficult, but they are quite easy once you get the hang of it. If all you need to know is whether or not a given number is prime, some of these might save you a lot of brute-force dividing.
• Does the number (2 or more digits, understood throughout) end in 2, 4, 5, 6, 8 or 0? If so, eliminate it; it is composite. You can divide it evenly by 2 or by 5 or both.
• Calculate the digital root of the number by adding all the number's digits as if they are individual one-digit numbers*. As soon as you get a two-digit sum, add the digits together. The digital root will be the final one-digit result. Is the digital root 3, 6 or 9? If so, eliminate it; it is composite.
• If the number has survived the above filters, divide it by 3. If it divides evenly, eliminate it; it is composite.
• If dividing by 3 leaves a remainder, divide it by 7. If it divides evenly, eliminate it; it is composite. [You don't have to divide by 5, since you have already filtered out its multiples (numbers ending in 5 and 0). And you don't have to divide by 9, because every multiple of 9, however big, will have a digital root equal to 9.]
• If the number has as a factor any number below 11, you have already eliminated it as composite. If the number has survived this far, you have to divide by odd numbers from 11 and up. You can eliminate odd numbers that have any factor between 3 and 9; you've already eliminated such numbers^. The number could be a composite that has all factors greater than 11.
• Theoretically, you only have to continue dividing until you reach the integer that is nearest to and less than the square root of the original number. If by that time you have found no evidence that the number can be divided evenly by any integer, then you have a Prime number.

  *The number 3571 is prime, and has a digital root of 7. 3+5= 8; 8+7=15; 15+1=16; and 1+6=7. You can add the digits in any order, and reduce the sum to one digit whenever you want. It will always be the same if you add correctly. Primes will never have a digital root of 3, 6 or 9! This doesn't mean that digital roots of 1, 2, 4, 5, 7 or 8 prove that the number is prime. Composite AND prime numbers can have these digital roots.

  ^So you don't have to divide by 15, since 15 has 3 as a factor. But you do have to divide by 17. You would divide by 11, 13, 17, 19, 23, etc. You would continue until you find a factor, or until you reach the integer closest to and less than (or equal to) the square root of the original number. You might say "Wait! I didn't actually divide by 15. How do I know I have eliminated it?" You have already eliminated 3, and 3 is a factor of 15. So if it can be divided evenly by 15, then you have already divided by 3 and should have gotten no remainder.

  The really hard thing to do, and it may in fact be impossible, is to find a mathematical formula for finding all primesby some method other than brute force. No one has done it yet.