## Twin Prime Range

Back to Programming

### Description

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]

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.

## 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.