Prime number algorithm

1 st method (very inefficient):

get value for an number n
if n =2, output “It is a prime number”
set the value i =2;
set the value isPrime = True;
if i if n % i == 0, isPrime=False;
else i + 1;
output “It is a prime number” if isPrime is true
output “It is a not prime number” if isPrime is False.

The above method is inefficient. If the input is a very big prime number, it will make division from 2 all the way to n-1.

2nd method (slightly faster):

If :
an integer x < another integer n,
√n % x != 0 (n is not divisible by x )
then: n² % x !=0 (n² is not divisible by x)

Vise versa, n % x == 0, then n² % x ==0 ;

So, we can implement the 1st method, by looping only from 2 to n. we just have to modify the above algorithm “i<n” into “i<√n”. it optimized (n ) algorithm into (√n) algorithm.

3rd method (Sieve of Eratosthene):
This method works when given a number n and get all the prime numbers that is smaller than n. It filters out all the composite numbers, and left the prime number.

It works in this way:

  1. given a number n,
  2. in the range of 2 to n, find the prime number one by one.
    • the first prime number is 2, then filter out all the numbers that is multiple of 2.
    • find the next prime number, which is 3, and filter out all the multiples of 3.
    • find the next prime number 5, and filter out all the multiples of 5.
    • continue the above process. until the searched prime number reaches n.
  3. output all the remaining numbers.

The pseudo code would be:

  1. given a number n, n>1
  2. define a list IsPrime[], indexed from 2 to n, initially all items are set to True
  3. i start from 2, if i < n, repeat the following steps:

if IsPrime[i] == true:

set IsPrime[ i2, i2+i, i2+2i, i2+3i, …] to False (not exceeding n)

      4.output the indices in IsPrime[] ‘s item that is true.

Run the Script in CodeSkulptor

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s