Circular Primes in Java
Circular primes are a special category of prime numbers that remain prime when their digits are cyclically rotated. In other words, a circular prime is a prime number that, when its digits are rearranged in any circular order, still results in a prime number. For example, 197, 971, and 719 are circular primes because all rotations of their digits (197, 971, and 719) are also prime.
Approach 1: Brute Force
The brute force approach for finding circular primes involves straightforward checking of each number and its circular rotations for primality. This method iterates through a range of numbers, checks whether each number and its circular rotations are prime, and collects circular primes into a list.
Algorithm
Step 1: Initialize Variables: Set the upper limit for searching circular primes (limit variable). Create an empty list to store circular primes.
Step 2: Iterate through each number from 2 to the specified limit. For each number, perform the following steps:
Step 2.1: Define a function isPrime to check if a given number is prime. If the number is less than 2, return false.
Step 2.2: Iterate through numbers from 2 to the square root of the given number. If the number is divisible by any of these values, return false. Otherwise, return true.
Step 3: Define a function rotate to rotate the digits of a given number to the left. Convert the number to a string to manipulate its digits.
Step 3.1: Rotate the string by moving the first character to the end. Convert the rotated string back to an integer and return it.
Step 4: Define a function isCircularPrime that takes a number as input. Initialize a variable rotated to the input number.
Step 5: Use a do-while loop to iterate through circular rotations until the original number is reached.
Step 5.1: Inside the loop, check if the current rotation (rotated) is not a prime number using the isPrime function. If not prime, exit the loop.
Step 6: Update rotated to the next circular rotation using the rotate function. If all rotations are prime, add the original number to the list of circular primes.
Step 7: Inside the main loop, check if the current number and all its circular rotations are circular primes using the isCircularPrime function.
Step 8: If a circular prime is found, add it to the list of circular primes. After the main loop, print the list of circular primes.
Filename: CircularPrimesBruteForce.java
public class CircularPrimesBruteForce {
public static void main(String[] args) {
int limit = 100; // Set the upper limit for searching circular primes
System.out.println("Circular primes below " + limit + ":");
for (int i = 2; i < limit; i++) {
if (isCircularPrime(i)) {
System.out.print(i + " ");
}
}
}
// Function to check if a number is prime
private static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Function to rotate the digits of a number
private static int rotate(int num) {
String numStr = Integer.toString(num);
String rotatedStr = numStr.substring(1) + numStr.charAt(0);
return Integer.parseInt(rotatedStr);
}
// Function to check if a number and its circular rotations are prime
private static boolean isCircularPrime(int num) {
int rotated = num;
do {
if (!isPrime(rotated)) {
return false;
}
rotated = rotate(rotated);
} while (rotated != num);
return true;
}
}
Output:
Circular primes below 100:
2 3 5 7 11 13 17 31 37 71 73 79 97
Time complexity
The main factor influencing the time complexity is the nested loop in the isCircularPrime function, which checks all circular rotations of a given number. The time complexity can be expressed as O(N * M), where N is the number of iterations in the main loop (from 2 to the specified limit). M is the maximum number of circular rotations to be checked for primality.
Space Complexity
The space complexity can be expressed as O(N), where N is the specified limit. This is because an array of size N is used to store boolean values indicating whether each number up to the limit is prime.
Approach 2: Sieve of Eratosthenes
The Sieve of Eratosthenes is a classical algorithm for finding all prime numbers up to a given limit. When applied to circular primes, the sieve helps efficiently generate a list of prime numbers, reducing the need for primality checks and improving overall performance. Instead of checking primality for each number individually, the sieve helps filter out composite numbers, significantly reducing the computational load.
Algorithm
Step 1: Create a boolean array isPrime of size limit and initialize all elements to true. Each index represents a number, and the value at the index is true if the number is considered prime.
Step 2: Starting from 2, iterate through the array. For each prime number found, mark its multiples as composite by setting the corresponding array elements to false.
Step 3: Define a function isPrime to quickly check whether a number is prime. If the number is less than 2, consider it not prime. Check the value in the isPrime array at the corresponding index.
Step 4: Circular Prime Checking Function (isCircularPrime): For each prime number generated by the Sieve, check if it is a circular prime.
Step 5: Rotate the digits of the number and check if the rotated numbers are prime using the isPrime function.
Step 6: If any rotation is not prime, the number is not a circular prime. Print or store the circular primes as they are found.
Filename: CircularPrimesSieve.java
import java.util.ArrayList;
import java.util.Arrays;
public class CircularPrimesSieve {
public static void main(String[] args) {
int limit = 100; // Set the upper limit for circular primes
boolean[] isPrime = sieveOfEratosthenes(limit);
System.out.println("Circular primes below " + limit + ":");
for (int i = 2; i < limit; i++) {
if (isPrime[i] && isCircularPrime(i)) {
System.out.print(i + " ");
}
}
}
// Function to generate primes using Sieve of Eratosthenes
private static boolean[] sieveOfEratosthenes(int limit) {
boolean[] isPrime = new boolean[limit];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i < limit; i++) {
if (isPrime[i]) {
for (int j = i * i; j < limit; j += i) {
isPrime[j] = false;
}
}
}
return isPrime;
}
// Function to rotate the digits of a number
private static int rotate(int num) {
String numStr = Integer.toString(num);
String rotatedStr = numStr.substring(1) + numStr.charAt(0);
return Integer.parseInt(rotatedStr);
}
// Function to check if a number and its circular rotations are prime
private static boolean isCircularPrime(int num) {
int rotated = num;
do {
if (!isPrime(rotated)) {
return false;
}
rotated = rotate(rotated);
} while (rotated != num);
return true;
}
// Function to check if a number is prime
private static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
}
Output:
Circular primes below 100:
2 3 5 7 11 13 17 31 37 71 73 79 97
Time Complexity
The time complexity of the Sieve of Eratosthenes is generally considered to be O(n log log n) where n is the upper limit for finding primes. This is because the algorithm iterates through each number up to the square root of the limit, marking its multiples as composite. The inner loop for marking multiples runs in linear time for each prime.
Space Complexity
The space complexity is O(n). The algorithm uses an array of size n to store the boolean values indicating whether each number is prime. The space required is proportional to the size of the input limit.
Approach 3: Recursive Circular Rotations
The Recursive Circular Rotations approach to finding circular primes involves generating all possible circular rotations of a given number through a recursive function. For each rotation, the primality is checked, and the original number is deemed a circular prime if all rotations are prime. This method provides an alternative way of handling circular rotations, utilizing recursion to systematically generate and verify each rotation.
Algorithm
Step 1: Set the upper limit for searching circular primes (limit variable), iterate through each number from 2 to the specified limit.
Step 2: For each number, perform the following steps:
Step 2.1: Define a function isPrime to check if a given number is prime. If the number is less than 2, return false.
Step 2.2: Iterate through numbers from 2 to the square root of the given number. If the number is divisible by any of these values, return false. Otherwise, return true.
Step 3: Define a function isCircularPrime that takes a number as input. Convert the number to a string (numStr).
Step 4: Initialize a HashSet (rotations) to store unique circular rotations. Call the generateRotations recursive function to populate the HashSet with all circular rotations.
Step 5: Iterate through the rotations in the HashSet, check if the current rotation is not a prime number using the isPrime function. If not prime, return false. If all rotations are prime, return true.
Step 6: Define a recursive function generateRotations that takes a string representation of a number (numStr) and a HashSet (rotations).
Step 7: If the current rotation is not already in the HashSet, add it to the HashSet and make a recursive call with the rotated string (numStr.substring(1) + numStr.charAt(0)) as the argument.
Step 8: Inside the main loop, check if the current number is a circular prime using the isCircularPrime function. If a circular prime is found, print the number.
Filename: RecursiveCircularPrimes.java
import java.util.HashSet;
public class RecursiveCircularPrimes {
public static void main(String[] args) {
int limit = 100;
System.out.println("Circular primes below " + limit + ":");
for (int i = 2; i < limit; i++) {
if (isCircularPrime(i)) {
System.out.print(i + " ");
}
}
}
// Function to check if a number is prime
private static boolean isPrime(int num) {
if (num < 2) {
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
return false;
}
}
return true;
}
// Recursive function to generate circular rotations and check primality
private static boolean isCircularPrime(int num) {
String numStr = Integer.toString(num);
HashSet<Integer> rotations = new HashSet<>();
generateRotations(numStr, rotations);
for (int rotation : rotations) {
if (!isPrime(rotation)) {
return false;
}
}
return true;
}
// Recursive function to generate circular rotations
private static void generateRotations(String numStr, HashSet<Integer> rotations) {
if (!rotations.contains(Integer.parseInt(numStr))) {
rotations.add(Integer.parseInt(numStr));
generateRotations(numStr.substring(1) + numStr.charAt(0), rotations);
}
}
}
Output:
Circular primes below 100:
2 3 5 7 11 13 17 31 37 71 73 79 97
Time Complexity
For each number, the generateRotations function recursively generates all circular rotations. The number of recursive calls is equal to the number of digits in the original number. Therefore, the time complexity can be expressed as O(d * N), where d is the maximum number of digits in any given number, and N is the limit for searching circular primes.
Space Complexity
The space complexity is primarily determined by the HashSet (rotations) used to store unique circular rotations for each number. In the worst case, where all circular rotations are unique, the space complexity can be O(d * N), where d is the maximum number of digits in any given number, and N is the limit for searching circular primes.
Approach 4: Dynamic programming
Dynamic programming is a problem-solving technique that involves breaking down a complex problem into smaller overlapping subproblems. Solutions to subproblems are computed only once and stored in a table or memorization array, which allows for efficient retrieval and avoids redundant computations. This technique is particularly useful when a problem exhibits optimal substructure and overlapping subproblems. In the context of circular primes, dynamic programming can be employed to optimize primality checks and avoid redundant calculations.
Algorithm
Step 1: Create a memoization array (memo) to store the results of primality checks for each number.
Step 2: Implement a function isPrime to check if a given number is prime. Use memorization to store and reuse the results of primality checks.
Step 3: Implement a function rotate to rotate the digits of a given number to the left. Implement a function isCircularPrime that takes a number as input.
Step 4: Use a loop to check all circular rotations of the number for primality. Utilize the isPrime function for primality checks.
Step 5: Iterate through numbers from 2 to the specified limit. Check if each number and its circular rotations are circular primes using the isCircularPrime function. Print or store circular primes as they are found.
Filename: DynamicProgrammingCircularPrimes.java
import java.util.Arrays;
public class DynamicProgrammingCircularPrimes {
public static void main(String[] args) {
int limit = 100;
System.out.println("Circular primes below " + limit + ":");
for (int i = 2; i < limit; i++) {
if (isCircularPrime(i, limit)) {
System.out.print(i + " ");
}
}
}
// Memoization array for primality checks
private static Boolean[] memo = new Boolean[100];
// Function to check if a number is prime
private static boolean isPrime(int num) {
if (memo[num] != null) {
return memo[num];
}
if (num < 2) {
memo[num] = false;
return false;
}
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
memo[num] = false;
return false;
}
}
memo[num] = true;
return true;
}
// Function to rotate the digits of a number
private static int rotate(int num) {
String numStr = Integer.toString(num);
String rotatedStr = numStr.substring(1) + numStr.charAt(0);
return Integer.parseInt(rotatedStr);
}
// Function to check if a number and its circular rotations are circular primes
private static boolean isCircularPrime(int num, int limit) {
int rotated = num;
do {
if (!isPrime(rotated) || rotated >= limit) {
return false;
}
rotated = rotate(rotated);
} while (rotated != num);
return true;
}
}
Output:
Circular primes below 100:
2 3 5 7 11 13 17 31 37 71 73 79 97
Time Complexity
The isCircularPrime function involves rotating digits and performing primality checks for each rotation. For each number, the time complexity is determined by the number of digits d and the number of circular rotations performed (in this case, up to d rotations). Therefore, the time complexity can be expressed as O(d^2 * N), where N is the limit for searching circular primes.
Space Complexity
The space complexity is influenced by the memoization array (memo) and the memoization array has a space complexity of O(N), where N is the limit for searching circular primes. This is because each number up to the limit is stored in the memoization array.