By Kardi Teknomo, PhD .

Is-Prime Algorithm

< Previous | Next | Content >

Algorithm to Test whether a number is a Prime or Not

Based on Sieve of Erastosthenes in the previous section, we can devise an algorithm to find out prime number. The algorithm below determines whether a positive integer number N larger or equal to 2 is a prime number or not:

Input: N >= 2 Set limit to be an integer that slightly lower than square root of N For I = limit to 2 If N mod I = 0 then Exit For Next I If I = 1 then Print "Prime" Else Print "Not Prime" End If

The flow chart of the Is Prime algorithm above is shown as follow

Is Prime Algorithm

Example of application: in cryptography, large prime number is used to send secret message.

In the next section , you will learn something fundamental in arithmetic that is very useful for many practical applications.

< Previous | Next | Content >

This tutorial is copyrighted .