5 Best Ways to Check if Every Rotation of a Number is Prime in Python

Rate this post

πŸ’‘ Problem Formulation: The challenge lies in creating a Python program to verify if every possible rotation of a given integer number results in a prime number. In essence, if we have an input number such as 197, the desired output would indicate whether 197, 971, and 719 are all prime numbers. The following methods offer various solutions for tackling this task, presenting different ways to achieve the goal while maintaining code readability, efficiency, and compactness.

Method 1: Brute Force Check

This method employs a brute force tactic: it generates all rotations of the number and checks each for primality. Using basic loops and conditional checks, it is straightforward but not the most efficient.

Here’s an example:

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def rotations(num):
    s = str(num)
    return [int(s[i:] + s[:i]) for i in range(len(s))]

def all_rotations_prime(num):
    return all(is_prime(rot) for rot in rotations(num))

# Example
num = 197
print(all_rotations_prime(num))

Output: True

The is_prime function checks if a number is prime, while rotations generates all rotations of a given number represented as a string. The all_rotations_prime function utilizes these to determine if all rotations of the input number are prime. The method is very explicit; however, it may suffer performance issues for large numbers due to the repeated prime checks.

Method 2: Sieve of Eratosthenes with Rotation Check

Using the classic Sieve of Eratosthenes to find all prime numbers up to the largest rotation, this method is more efficient for checking multiple numbers, as the sieve is computed only once.

Here’s an example:

def sieve(n):
    prime = [True for _ in range(n+1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p * p, n+1, p):
                prime[i] = False
        p += 1
    prime[0], prime[1] = False, False
    return prime

def all_rotations_prime(num, primes):
    s = str(num)
    return all(primes[int(s[i:] + s[:i])] for i in range(len(s)))

# Define the range
max_rot = 1000  # Adjust based on the expected maximum rotation
primes = sieve(max_rot)

# Example
num = 197
print(all_rotations_prime(num, primes))

Output: True

In this code snippet, the sieve function initializes a list of boolean values that designate primality and filters out non-prime numbers starting from 2. The all_rotations_prime function checks if all rotations of a number are in the prime list. The strength of this method is its superior efficiency when checking many numbers against a pre-calculated list of primes.

Method 3: Incremental Rotation and Prime Check

This method balances between generating all rotations at once and checking each immediately for primality, allowing for quick exits if a non-prime rotation is found.

Here’s an example:

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def all_rotations_prime(num):
    s = str(num)
    for i in range(len(s)):
        if not is_prime(int(s[i:] + s[:i])):
            return False
    return True

# Example
num = 197
print(all_rotations_prime(num))

Output: True

Here, the is_prime function determines the primality of individual rotations, which are generated incrementally within the all_rotations_prime loop. If a non-prime rotation is encountered, the function immediately returns False, potentially saving computation time compared to generating all rotations beforehand.

Method 4: Using itertools and Set for Uniqueness

While the previous methods rely on string manipulation, this approach employs itertools to generate unique rotations and sets to prevent duplicate prime checks, enhancing performance.

Here’s an example:

from itertools import permutations

def is_prime(num):
    if num <= 1:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def all_rotations_prime(num):
    digits = str(num)
    unique_rotations = set(int(''.join(p)) for p in permutations(digits, len(digits)))
    return all(is_prime(rot) for rot in unique_rotations)

# Example
num = 197
print(all_rotations_prime(num))

Output: True

Using permutations from the itertools library, we generate all possible orderings of the number’s digits and create a set to maintain only unique rotations. The all_rotations_prime function then checks each rotation’s primality. This method optimizes for numbers with repeating digits, where rotations could be identical.

Bonus One-Liner Method 5: Utilizing Python’s Standard Library

This sleek one-liner combines previous methods’ logic and Python’s built-in features to provide a concise yet potent solution.

Here’s an example:

from sympy import isprime
from itertools import permutations

# One-liner
all_rotations_prime = lambda num : all(isprime(int(''.join(p))) for p in set(permutations(str(num))))

# Example
num = 197
print(all_rotations_prime(num))

Output: True

This code snippet leverages the sympy library’s isprime function for primality testing and permutations combined with a set to handle rotations. Wrapped in a lambda, it becomes a single-line declaration that is expressive and compact, showcasing the power of functional programming combined with Python’s comprehensive standard library.

Summary/Discussion

  • Method 1: Brute Force Check. Easy to understand but can be inefficient for large numbers due to repetitive prime checks.
  • Method 2: Sieve of Eratosthenes with Rotation Check. Efficient for batch checking multiple numbers using a pre-computed prime sieve; less ideal for one-off computations.
  • Method 3: Incremental Rotation and Prime Check. Offers a balanced approach by checking rotations immediately, saving time if a non-prime is found early.
  • Method 4: Using itertools and Set for Uniqueness. Efficiently handles numbers with repeating digits, as sets ensure computations for unique rotations only.
  • Method 5: Python’s Standard Library in a One-Liner. A condensed expression of prior methods, utilizing powerful library functions for a concise solution.