**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:

- given a number n,
- 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.

- output all the remaining numbers.

The pseudo code would be:

- given a number n, n>1
- define a list IsPrime[], indexed from 2 to n, initially all items are set to True
- 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.

I have scripted it in python. To see the code and test it in codeSkulptor, please click the link below.

http://www.codeskulptor.org/#user41_lovrNkO0EW_4.py

**Reference:**

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

https://codility.com/programmers/lessons/9/

https://codility.com/media/train/8-PrimeNumbers.pdf

http://research.cs.wisc.edu/techreports/1990/TR909.pdf

———————————————–

Designed by Freepik

### Like this:

Like Loading...

*Related*