# Circular Prime – Solution of ISC Computer Practical 2016

## ISC Computer Science Practical 2016, Question 1

A Circular Prime is a prime number that remains prime under cyclic shifts of its digits. When the leftmost digit is removed and replaced at the end of the remaining string of digits, the generated number is still prime. The process is repeated until the original number is reached again.
A number is said to be prime if it has only two factors 1 and itself.

Example:
131
311
113
Hence, 131 is a circular prime.

Test your program with the sample data and some random data:

Example 1

```INPUT:  N= 197
OUTPUT:
197
971
719

197 IS A CIRCULAR PRIME```

Example 2

```INPUT:  N= 1193
OUTPUT:
1193
1931
9311
3119

1193 IS A CIRCULAR PRIME```

Example 3

```INPUT:  N= 29
OUTPUT:
29
92

29 IS NOT A CIRCULAR PRIME
```

## An efficient Java implementation for circular prime problem is as follows:

```import java.util.*;
class CircularPrime{
public static boolean isPrime( int number ){
int factorCount = 0;
if( number < 2 ) return false;
else if( number == 2 ) return true;
else if( number % 2 == 0 ) return false;
else{
int limit = (int) Math.sqrt( number );
for( int i = 3 ; i <= limit ; i+=2 ){
if( number %i == 0 ){
return false;
}
}
}
return true;
}

public static int circulate( int n, int divisor ){
//left most digit is n/divisor;
//remainder after removing left most is n%divisor;
if( n < 10 )
return n;
else return ( n % divisor ) * 10 + n / divisor;
}
public static void main( String args[] ){
int N, digit;
Scanner sc = new Scanner( System.in );
System.out.print("INPUT: N= ");
N = sc.nextInt();
int numOfDigits = 0, divisor=1, circular=N;
boolean allPrime = true, isValidDigit=true;
for( int temp = N; temp > 0; temp /= 10 ){
numOfDigits++;
divisor *=10;
digit=temp%10;
if( !(digit==1 || digit==3 || digit==7 || digit==9) ) {
isValidDigit=false;
break;
}
}
if(!isValidDigit && numOfDigits>=2){
System.out.println( N + " IS NOT A CIRCULAR PRIME" );
}else{
divisor /=10;
System.out.println( "OUTPUT: " );
do{
System.out.println( "        "+circular );
circular = circulate( circular, divisor );
if( !isPrime( circular ) ) allPrime=false;
}while( circular != N );
System.out.print( "\n        " );
if( allPrime ) System.out.println( N + " IS A CIRCULAR PRIME" );
else System.out.println( N + " IS NOT A CIRCULAR PRIME" );
}
}
}```

Note: A circular prime with at least two digits can only consist of combinations of the digits 1, 3, 7 or 9, because having 0, 2, 4, 6 or 8 as the last digit makes the number divisible by 2, and having 0 or 5 as the last digit makes it divisible by 5.

Please note that in the above solution the number N is an integer and all operations are performed which is computationally better (efficient) than converting between string and integer for circulating the number.

The function isPrime also uses a number of optimization for efficiently determining if the number is a prime number or not. For details of the isPrime() function refer to my earlier post on primality i.e. Prime time.

## 2 thoughts on “Circular Prime – Solution of ISC Computer Practical 2016”

1. aby

Try the number 70 for the circular prime program.
It won’t work.

1. Vinay Singh Post author

Thank you for pointing out the mistake. I have modified the program to remove the anomaly.

This site uses Akismet to reduce spam. Learn how your comment data is processed.