Prime Numbers Algorithm
Introduction:
Prime numbers are Natural numbers which have only two factors, one and the number itself.If a number 'b' is a factor of 'a' then 'a' is divisible by 'b'.
prime numbers : 2, 3, 5, 7, 11, 13, 17, 19, .....
prime numbers are essential for encryption and encryption is essential for safe online business and communication. The algorithm used is called RSA Algorithm. Before studying complex algorithms like RSA algorithms, one may begin by learning algorithms to solve simple problems related to primes like the one stated below..
Problem Statement:
check whether a given number is prime or not.
Go through Algorithms 1, 2, 3 to understand with the help of the pseudo code and code given, how the above problem can be solved.
Also go through the given problem 1 and its solution(s) to see how the above Algorithms are helpful in solving various problems related to primes
Go through Resources to find various online videoes books web pages etc., for further reference and study.
Algorithm 1 : Naive Algorithm
we are given a number n .
obviously n is divisible by one and itself.
So , we check if there exists any number between 1 and n that divides n.
If it exists then n is not prime
otherwise n is prime.
Pseudo code :
IsPrime :
if n < 2 :
return false
if n==2 :
return true
for i = 3 to n :
if n is divisible by i :
return false
return true
Code :
// code to check if a given number is prime
// naive algorithm
// complexity O(n)
#include <stdio.h>
#include <stdbool.h>
bool IsPrime(int n)
{
if (n < 2)
{
return false;
}
else if (n == 2)
{
return true;
}
for (int i = 2; i < n; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
if (IsPrime(n))
{
printf("%d is a prime number\n", n);
}
else
{
printf("%d is not a prime number\n", n);
}
}
Complexity Analysis :
we see that the algorithm has to go through n steps if n is prime else it is less than n but has an upper bound of O(n). Hence Time complexity is O(n).
Algorithm 2
In algorithm 1, we ran the loop for all n numbers..can we optimize it ?
Assume n = a.b for a, b ∈ (1,n)
Then we can say that one of a or b is less than or equal to n/2 .
Hence checking only upto n/2 is enough
Pseudo code :
IsPrime :
if n < 2 :
return false
if n==2 :
return true
for i = 3 to n/2 :
if n is divisible by i :
return false
return true
Code :
// code to check if a given number is prime
// algorithm
// complexity O(n/2)
#include <stdio.h>
#include <stdbool.h>
bool IsPrime(int n)
{
if (n < 2)
{
return false;
}
else if (n == 2)
{
return true;
}
for (int i = 2; i <= n / 2; i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
if (IsPrime(n))
{
printf("%d is a prime number\n", n);
}
else
{
printf("%d is not a prime number\n", n);
}
}
Complexity Analysis :
we see that the algorithm has to go through n/2 steps if n is prime but has an upper bound of O(n/2). Hence Time complexity is O(n/2).
Algorithm 3: Optimized algorithm for checking primality
In algorithm 2, we ran the loop for all n/2 numbers..let's see if we can optimize it further.
Mathematically, it is proven that checking only upto √ n is enough to check if a number is prime or not. Therefore we don't have to run the loop for all n/2 numbers. Thus optimising the algorithm further.
Pseudo code :
IsPrime :
if n < 2 :
return false
if n==2 :
return true
for i = 3 to √n :
if n is divisible by i :
return false
return true
Code :
// code to check if a given number is prime
// algorithm
// complexity O(sqrt(n))
// compile: gcc prime3.c -lm
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool IsPrime(int n)
{
if (n < 2)
{
return false;
}
else if (n == 2)
{
return true;
}
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
if (IsPrime(n))
{
printf("%d is a prime number\n", n);
}
else
{
printf("%d is not a prime number\n", n);
}
}
Complexity Analysis :
we see that the algorithm has to go through √n steps if n is prime but has an upper bound of O(√n). Hence Time complexity is O(√n).
solution 1
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool IsPrime(int n)
{
if (n < 2)
{
return false;
}
else if (n == 2)
{
return true;
}
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int main()
{
int n;
printf("Enter a number: ");
scanf("%d", &n);
for(int i=2;i<n;i++)
{
if(IsPrime(i))
{
printf("%d ",i);
}
}
printf("\n");
}
Solution 2
// printing all primes less than n
// seive of Eratosthene
#include <stdio.h>
#include <stdbool.h>
void seive_of_eratosthene(int n)
{
// initializing
bool prime[n + 1];
for (int i = 0; i < n + 1; i++)
{
prime[i] = true; // assume that everything is prime
}
// main part
for (int i = 2; i < n; i++)
{
if (prime[i]) // i is prime
{
for (int j = i * i; j <= n; j += i) // only from i*i since i*k for k<i are already covered by previous ones
{
prime[j] = false; // multiples of i are not primes
}
}
}
// console output
for (int i = 2; i <= n; i++)
{
if (prime[i])
{
printf("%d ", i);
}
}
printf("\n");
}
int main()
{
int n;
printf("Enter n: ");
scanf("%d", &n);
seive_of_eratosthene(n);
}