Is-Prime Algorithm

By Kardi Teknomo, PhD.

<Previous | Next | Content>

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

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.

Preferable reference for this tutorial is

Teknomo, Kardi (2010) Prime factor tutorial. http:\\people.revoledu.com\kardi\ tutorial\BasicMath\Prime\