FOR FREE CONTENT
Circular Prime
Back to ProgrammingDescription
A number is said to be circular prime if the number itself is a prime number and all possible permutations of the number is prime.
For example, if we consider a number 113, the number is a prime number, the permutations of this number are 131, 311, both of them are also prime. Therefore, the number 113 is a circular prime number.
Algorithm
INPUT: A number
OUTPUT: Whether the number is circular prime number or not.
PROCESS:
Step 1: [Taking the input]
Read n [the number to be checked]
Step 2: [Function to check whether a number ‘n’ is a prime number]
Set c<-0
[Counting the number of factors]
For i=1 to n repeat
If n mod i=0 then
Set c<-c+1
[End of ‘if’]
[End of ‘for’ loop]
[Checking for prime number]
If c=2 then
Return 1
Else
Return 0
[End of ‘if’]
[End of the function]
Step 3: [Function to check whether a number is a circular prime number or not]
Set c<- 0
Set tmp<-n
While tmp>0 repeat
Set c<-c+1
Set tmp<-tmp / 10
[End of ‘while’ loop]
Set num <- n
[while each permutation of the number is prime]
While prime(num)=1 repeat
Set r<- num mod 10
Set d <- num / 10
Set num <- (10c - 1) × r + d
[After checking all the permutations if we get the original number back]
If num = n then
Return 1
[End of ‘if’]
[End of ‘while’ loop]
Return 0
[End of the function]
Step 4: [Calling the function to check for ‘circular prime’]
If circular(n)==1 then
Print "The number is a circular prime number"
Else
Print "The number is not a circular prime number"
[End of ‘if’]
Step 5: Stop.
Code
Time Complexity:
while (prime(num))
{
r= num % 10;
d = num / 10;
num = (pow(10, c - 1)) * r + d;
//After checking all the permutations if we get the original
//number back
if (num == n)
return 1;
}
The time complexity to check for circular prime is O() where ‘n’ is the number to be checked as circular prime. The time complexity to check for a prime number is O(m) in this program where ‘m’ is the number that is to be checked for prime.
