💡 Problem Formulation: Two integers are considered cousin primes if they are both prime and have a difference of 4 between them. For instance, if we have the numbers 7 and 11, the desired output is true, indicating they are cousin primes, because both are prime and their difference is 11 – 7 = 4.
Method 1: Brute Force Check
This method involves checking each number individually to determine if they are prime, and then checking if their difference is exactly 4. The function is_prime() is used to determine the primality of each number. Then the difference of the two numbers is computed and checked if it equals 4.
Here’s an example:
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
def are_cousin_primes(num1, num2):
return is_prime(num1) and is_prime(num2) and abs(num1 - num2) == 4
print(are_cousin_primes(7, 11))
Output:
True
This code defines a function for primality testing, then defines a function that uses this test for both numbers and checks if their absolute difference is 4. It is a straightforward approach that works well for small numbers but may not be efficient for large integers.
Method 2: Sieve of Eratosthenes Optimization
Method 2 uses the Sieve of Eratosthenes algorithm to create a list of prime numbers up to a certain value, then checks if the given numbers are in that list and their difference is 4. This method is more efficient for checking multiple pairs of numbers.
Here’s an example:
def sieve(n):
primes = [True for i in range(n+1)]
p = 2
while (p * p <= n):
if primes[p] == True:
for i in range(p * p, n+1, p):
primes[i] = False
p += 1
return primes
def are_cousin_primes(num1, num2, primes):
return primes[num1] and primes[num2] and abs(num1 - num2) == 4
primes = sieve(100)
print(are_cousin_primes(7, 11, primes))
Output:
True
After generating a list of primes using the sieve method, we simply check if our numbers are prime by looking them up in the list. We then verify their difference is four. This method is very fast when checking large ranges or many pairs of numbers.
Method 3: Memoization
Memoization is an optimization technique where we store the results of expensive function calls and return the cached result when the same inputs occur again. In this case, we memoize the results of prime checks to quickly determine cousin primes.
Here’s an example:
from functools import lru_cache
@lru_cache(maxsize=None)
def is_prime(num):
if num < 2:
return False
for i in range(2, int(num**0.5) + 1):
if num % i == 0:
return False
return True
def are_cousin_primes(num1, num2):
return is_prime(num1) and is_prime(num2) and abs(num1 - num2) == 4
print(are_cousin_primes(7, 11))
Output:
True
Here, the is_prime function is decorated with lru_cache, which caches its return values. Repeated calls with the same arguments will return the cached results, which can significantly speed up the process for multiple checks.
Method 4: Probabilistic Primality Tests
In this method, probabilistic primality tests, such as the Miller-Rabin test, are used to determine if the numbers are prime. This method can quickly identify non-prime numbers, making it suitable for very large numbers, though it has a small chance of error.
Here’s an example:
import random
def miller_rabin(n, k=7):
if n == 2 or n == 3:
return True
if n <= 1 or n % 2 == 0:
return False
# find r and s
s, r = 0, n - 1
while r & 1 == 0:
s += 1
r //= 2
# do k tests
for _ in range(k):
a = random.randrange(2, n - 1)
x = pow(a, r, n)
if x != 1 and x != n - 1:
j = 1
while j < s and x != n - 1:
x = pow(x, 2, n)
if x == 1:
return False
j += 1
if x != n - 1:
return False
return True
def are_cousin_primes(num1, num2):
return miller_rabin(num1) and miller_rabin(num2) and abs(num1 - num2) == 4
print(are_cousin_primes(7, 11))
Output:
True
This code implements the Miller-Rabin primality test, which has a high probability of accurately determining whether a number is prime, especially for large numbers. When used to check cousin primes, it can provide very fast results.
Bonus One-Liner Method 5: Using Python’s sympy Library
Python’s sympy library provides a built-in method for prime checking. This one-liner approach lets you evaluate cousin primes quickly and effectively with minimal code.
Here’s an example:
from sympy import isprime are_cousin_primes = lambda num1, num2: isprime(num1) and isprime(num2) and abs(num1 - num2) == 4 print(are_cousin_primes(7, 11))
Output:
True
This compact lambda function uses sympy‘s isprime function to check the primality of the numbers and then verifies if their absolute difference is 4. It is the simplest and most Pythonic way to solve the problem, assuming sympy is installed.
Summary/Discussion
- Method 1: Brute Force Check. Easy to understand and implement. Not very efficient for very large numbers.
- Method 2: Sieve of Eratosthenes Optimization. Highly efficient when multiple checks are needed. Requires an upper limit for the sieve, and initial setup can be time-consuming for very large lists of primes.
- Method 3: Memoization. Speeds up repeated checks with the same numbers. Requires extra memory to store the results.
- Method 4: Probabilistic Primality Tests. Fast for large numbers. Might produce incorrect results, though the probability is very low with an adequate number of rounds.
- Method 5: Sympy Library. Very simple one-liner with a dependency on an external library. Ideal for concise scripts where performance is not the primary concern.