Make your own free website on Tripod.com
  Determining Prime Numbers

 

Home
About Us
Discussions
Quizzes
Reflections
Flowcharts
C Programs
Feedback

 

Positive whole numbers, otherwise known as integers, can be classified into two types: prime or composite. A number is said to be prime if it has no other divisor except 1 and itself. For example, 17 is a prime number since there is no whole number that can divide it and produce an integer quotient other than 1 and 17.

Otherwise, the number is composite, pertaining to the fact that it is divisible by positive numbers that are not equal to one or itself. An instance is the number 24, which is divisible by 2, 3, 4, 6, 8 and 12 aside from 1 and 24.

Note that zero and one are neither prime nor composite, thus they are known to be special numbers.


Here are some examples:

Example 1: 27

27 is equal to 9 x 3 and 1 x 27. Having four divisors, it is classified as a composite number.

Example 2: 36

36 is equivalent to 6 x 6, 9 x 4, 18 x 2, 12 x 3 and 36 x 1. Thus it is a composite number.

A good rule to remember is that all even numbers or multiples of 5 (those digits ending with 5 or 0) are composite, since they are divisible by 2 and 5 respectively.

Example 3: 23

The number only has two divisors: 23 and 1. Aside from those, none can be found (unless you consider decimals, but prime and composite numbers only apple to positive whole numbers). Hence it is a prime number.


But what if you are given a number so large you cannot decipher whether it is prime or composite...and you only have two minutes to answer? This is when the following methods of testing a prime number comes into the frame.

The Divisibility Test

This test can be done if you are well and truly acquainted with all the divisibility rules as listed below (but there are more aside from that!):

  • A number is divisible by 2 if the last digit is even.

  • A number is divisible by 3 If the sum of the digits is divisible by 3 as well.

  • A number is divisible by 4 if the last two digits form a number divisible by four.

  • A number is divisible by 5 if the last digit of the number is a 5 or a 0.

  • A number is divisible by 6 If the number is divisible by both 3 and 2.

  • Take the last digit, double it, and subtract it from the rest of the number; if the answer is divisible by 7 (including 0), then the number is also.

  • A number is divisible by 8 if the last three digits form a number divisible by eight.

  • A number is divisible by 9 if the sum of the digits is also divisible by 9.

  • A number is divisible by 10 if the number ends in 0.

  • Alternately add and subtract the digits from left to right. If the result is (including 0) is divisible by 11, the number is also.

  • A number is divisible by 12 if the number is divisible by both 3 and 4.

  • Delete the last digit from the number, then subtract 9 times the deleted digit from the remaining number. If what is left is divisible by 13, then so is the original number.

This test involves only one single step: test whether all numbers below the given number divides the latter. For example, 13 cannot be divided by any number lower that itself except 1. Thus it is prime.

Here is another example:

37

  • Since 2 does not divide 37, it is not divisible by any multiple of 2.

  • Since 3 does not divide 37, it is not divisible by any multiple of 3.

  • Since 5 does not divide 37, it is not divisible by any multiple of 5.

The above pattern of non-divisibility goes on until you reach the number 37, thus it is prime.

However, if you are given a number like 367, this method becomes impractical, hasty and downright time-wasting. This is when you use the second method.

The Prime Number Test

This test is relatively more practical since you only have to get the square root of the number (rounded off) and test all prime numbers below it for divisibility. If none divides the given number, it is prime.

Let us work on the example given earlier:

367

The square root of 367 is 19.15724, which can be rounded off as 19.

  • 367 divided by 19 does not produce an integer value, so we proceed to the next lower prime number.

  • 367 divided by 17 does not produce an integer value, so we proceed to the next lower prime number.

  • 367 divided by 13 does not produce an integer value, so we proceed to the next lower prime number.

This goes on until you reach the lowest prime number - 2. Hence the given number is prime.


CLICK HERE FOR QUIZ

Home | Determining Prime Numbers | Prime Factorization | Getting the Number of Divisors | The Sum and Product of Divisors

 

Copyright 2006. All rights reserved.

No part of this site may be reproduced without the permission of the authors.