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):
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.
Run the Script in CodeSkulptor