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
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.