Tests for Prime and Composite numbers

A test or procedure to check whether a given natural number is prime or not is known as a Primality Test. A primality test can also be used to find whether a given natural number is composite or not with this simple idea: If the number is not prime and not 1, then it is composite.

Following subsections discuss some algorithms/procedures for primality tests and finding prime numbers.

Basic Primality Test

This is the easiest primality test. It is based on the fact that if a natural number n is prime, then there must be no factor between 1 and the number. Here it is

Given a natural number ‘n’

• If n = 1, it is not prime (neither composite).
• Else, try to divide n by each natural number between 1 and n. If a factor is found, then n is not prime (composite) else it is prime.

Efficient Primality Test

It is known that all the factors of a natural number n other than n are smaller than or equal to √n. So, we can make the basic primality test more efficient by just trying to find the factors from 1 to √n instead of 1 to n. Here is the algorithm/procedure

Given a Natural Number ‘n’

• If n = 1, it is not prime (neither composite).
• Else, try to divide n by each natural number between 1 and √n. If a factor is found, then n is not prime (composite) else it is prime.

Note: This procedure is very fast compared to basic primality test. We only require a maximum of √n steps where basic primality test requires a maximum of n steps. For example, this procedure requires only 10 steps where the basic one requires 100 steps! The procedure becomes more and more beneficial as the size of n becomes larger.

Eratosthenes Sieve

This is an ancient algorithm/procedure for finding prime numbers. When we want to find all the prime numbers up to a certain limit n > 1, this is a convenient and very efficient algorithm. Here is the algorithm –

Step 1: List all the numbers from 2 to n.

Step 2: Circle the first uncrossed number and then cross all the multiples of the number.

Step 3: Repeat Step 2 until all the numbers in the list are either crossed or circled.

Step 4: Now the circled numbers are prime numbers, and the crossed ones are composite numbers.

Refer to solved question 9 for a demo of this procedure.

Prime and Composite Numbers are commonly used classifications of Natural Numbers based on divisibility and the number of Factors. A Prime Number has only two factors while Composite Numbers have more than two factors. This classification of Numbers makes the study of natural numbers more organized and convenient and is useful in a variety of situations like computer algorithms, biology, understanding of Number Theory, etc.

This article describes what are prime and composite numbers, the types of primes and composite numbers, and tests to check whether a given number is prime or not (primality tests). Finally, a few solved questions, and a few practice problems related to prime and composite numbers are presented.