CREATE OWN LIBRARY
Twin Prime Range
Back to ProgrammingDescription
Twin prime numbers are two prime numbers whose difference is 2, and both the numbers are prime numbers.
If both the numbers are prime but the difference is not 2, then the pair of the numbers is not twin prime.
The twin prime numbers are (3, 5), (5, 7), (11, 13) etc.
But (2, 3), (7, 11) these pairs are not twin prime as the difference between two is not 2.
Algorithm
INPUT: The ranges between which the prime numbers are to be found
OUTPUT: The twin primes between the ranges
PROCESS:
Step 1: [Taking the inputs]
Read p, q
Step 2: [Finding the ‘twin prime’]
For k=p to q repeat
Set c<-0
Set m<-k
Set n<-k+2
[Checking for twin prime]
If absolute value of (m-n)=2 then
[Checking if m is a prime number]
For i=1 to m repeat
If m mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
[If the 1st number is prime then check for another number]
If c=2 then
Set c<-0
For i=1 to n repeat
If n mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
[Checking if n is a prime number]
If c=2 then
Print m, n
[End of ‘if’]
[End of ‘if’]
[End of ‘if’]
[End of ‘for’ loop]
Step 3: Stop.
Code
TIME COMPLEXITY:
for(k=p;k<=q;k++)--------------------------------------------O(c)
{
c=0;
m=k;
n=k+2;
//checking for twin prime
if(abs(m-n)==2)---------------------------------------O(1)
{
//checking if m is a prime number
for(i=1;i<=m;i++)--------------------------O(m)
{
if(m%i==0)-----------------------O(1)
c++;
}
//if the 1st number is prime then check for another number
if(c==2)----------------------------------------O(1)
{
c=0;
for(i=1;i<=n;i++)----------------O(n)
{
if(n%i==0)-------------O(1)
c++;
}
//checking if n is a prime number
if(c==2)---------------------------O(1)
printf("(%d,%d) ",m,n);
}
}
}
The time complexity of this program is O(c*(m+n)) where ‘c’ is the number of elements in the range and ‘m’ and ‘n’ are two numbers to be checked as twin prime.
SPACE COMPLEXITY:
The space complexity of this program is O(1) as it requires a constant number of memory spaces for any given input.
