Circular Prime Program in Java and Python
ISC 2016 Question 1 circular prime solution with algorithm, explanation, Java program and simple Python program.
Download the complete ISC 2016 Computer Science Paper 2 (Practical).
Question:
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.
Test your program with the sample data and some random data.
Algorithm:
Step 1: Start.
Step 2: Accept a number n from the user.
Step 3: Store n in another variable a so that rotations can be performed without losing the original number.
Step 4: Initialize a flag variable as 0 to remember whether any rotation is not prime.
Step 5: Display the current value of a.
Step 6: Check whether a is prime using a separate prime-checking method.
Step 7: In the prime-checking method, count how many numbers from 1 to a divide a exactly.
Step 8: If the number of factors is not 2, set the flag to 1.
Step 9: Circulate the digits of a by moving its first digit to the end.
Step 10: Repeat Steps 5 to 9 until the circulated number becomes equal to the original number n.
Step 11: If the flag is 1, display that n is not a circular prime.
Step 12: Otherwise, display that n is a circular prime.
Step 13: Stop.
Explanation:
A circular prime must satisfy two conditions. First, the original number must be prime. Secondly, every cyclic rotation of its digits must also be prime. For example, the number 197 gives the rotations 197, 971 and 719. Since all three numbers are prime, 197 is a circular prime. On the other hand, 29 gives the rotations 29 and 92. Although 29 is prime, 92 is not prime, so 29 is not a circular prime.
The program separates the work into user-defined methods. The isPrime() method checks whether a number has exactly two factors. It counts all divisors from 1 to the number itself. If the count is 2, the number is prime; otherwise, it is not prime. This is a simple and direct method suitable for school-level practical programs, because students can easily dry-run the divisor counting process.
The circulate() method handles digit rotation. It converts the number into a string, removes the first character using substring(1), and then adds that first character at the end. For 1193, the first circulation produces 1931. The next circulations produce 9311 and 3119. Once 3119 is circulated again, it returns to 1193, which tells the program that all rotations have been checked.
The circular-prime method uses a do while loop because the original number must also be printed and tested before any rotation takes place. A flag variable is used to remember whether any generated number is not prime. Even if one rotation fails the prime test, the flag becomes 1. After the loop returns to the original number, the flag decides the final message. If no rotation failed, the number is declared a circular prime; otherwise, it is not a circular prime.
Java Program:
/**
* The class CircularPrime_Q1_ISC2016 inputs a number and checks whether
* it is a circular prime or not.
* @author : www.guideforschool.com
* @Program Type : BlueJ Program - Java
* @Question Year : ISC Practical 2016 Question 1
*/
import java.util.Scanner;
class CircularPrime_Q1_ISC2016
{
boolean isPrime(int n)
{
int count = 0;
// Count the number of exact factors of n.
for(int i = 1; i <= n; i++)
{
if(n % i == 0)
{
count++;
}
}
return count == 2;
}
int circulate(int n)
{
String s = Integer.toString(n);
/*
* Move the first digit to the end.
* Example: 197 becomes 971.
*/
String rotated = s.substring(1) + s.charAt(0);
return Integer.parseInt(rotated);
}
void isCircularPrime(int n)
{
int flag = 0;
int a = n;
/*
* The original number must also be checked, so a do-while loop
* is used before the first circulation is performed.
*/
do
{
System.out.println(a);
if(isPrime(a) == false)
{
flag = 1;
}
a = circulate(a);
}while(a != n);
if(flag == 1)
System.out.println(n + " IS NOT A CIRCULAR PRIME");
else
System.out.println(n + " IS A CIRCULAR PRIME");
}
public static void main(String args[])
{
CircularPrime_Q1_ISC2016 ob = new CircularPrime_Q1_ISC2016();
Scanner sc = new Scanner(System.in);
System.out.print("Enter a number: ");
int n = sc.nextInt();
ob.isCircularPrime(n);
}
}Equivalent Python Program:
def is_prime(n):
count = 0
# Count the number of exact factors of n.
for i in range(1, n + 1):
if n % i == 0:
count = count + 1
return count == 2
def circulate(n):
s = str(n)
# Move the first digit to the end.
rotated = s[1:] + s[0]
return int(rotated)
n = int(input("Enter a number: "))
a = n
flag = 0
while True:
print(a)
if is_prime(a) == False:
flag = 1
a = circulate(a)
# Stop after all rotations have been checked.
if a == n:
break
if flag == 1:
print(str(n) + " IS NOT A CIRCULAR PRIME")
else:
print(str(n) + " IS A CIRCULAR PRIME")Output:
Leave a Reply
Your email address will not be published. Comments are reviewed before appearing publicly.