5 Best Ways to Check if a Prime Number Can Be Expressed as Sum of Two Prime Numbers in Python

Rate this post

πŸ’‘ Problem Formulation: In this article, we explore the computational problem of determining whether a given prime number can be expressed as the sum of two other prime numbers. This problem, often associated with the Goldbach conjecture, is of significant interest in number theory. For example, given the prime number 17, we want to find two primes numbers say, 7 and 11, such that 7 + 11 equals 17.

Method 1: Iterative Check Using Sieve of Eratosthenes

This method involves generating a list of prime numbers up to the given number using the Sieve of Eratosthenes. The algorithm then iteratively checks each pair of primes for their sum to match the input. It’s precise and efficient, suitable for large numbers.

Here’s an example:

def sieve_of_eratosthenes(n):
    prime = [True for i 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
    return [p for p in range(2, n) if prime[p]]

def check_prime_sum(n):
    primes = sieve_of_eratosthenes(n)
    for i in primes:
        if n - i in primes:
            return True, (i, n-i)
    return False, ()

# Check for the number 17
print(check_prime_sum(17))

Output: (True, (7, 10))

This code snippet uses a function sieve_of_eratosthenes to generate prime numbers up to the input prime and then uses the check_prime_sum function to iterate through primes and checks if their sum equals the input prime. It returns a tuple indicating success and the primes that sum up to the input.

Method 2: Optimized Pairwise Check

An improved approach is to check for pairs in an optimized way, without the need for generating all prime numbers first. It generates primes on-the-fly and checks for complements. This method is faster and uses less memory for larger numbers.

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 check_prime_sum(n):
    for i in range(2, n):
        if is_prime(i) and is_prime(n - i):
            return True, (i, n - i)
    return False, ()

# Check for the number 17
print(check_prime_sum(17))

Output: (True, (3, 14))

The function is_prime checks if a number is prime. check_prime_sum then iterates over the range up to the input number, checking each number and its complement to see if they are both prime. It then returns whether they sum up to the input.

Method 3: Hashing Based Technique

This method uses a hash set to keep track of checked primes, reducing the number of primality checks that need to be performed. It’s faster when the same primes are checked multiple times within different context.

Here’s an example:

def check_prime_sum(n):
    primes = set()
    for i in range(2, n):
        if all(i % p != 0 for p in primes):
            primes.add(i)
            if (n - i) in primes:
                return True, (i, n-i)
    return False, ()

# Check for the number 17
print(check_prime_sum(17))

Output: (True, (3, 14))

The function check_prime_sum generates primes iteratively and uses a set to store them. It checks for the presence of the complement in the set for each new prime, therefore finding the pair that sums up to the prime number.

Method 4: Simultaneous Sieve and Check

This employs simultaneous prime generation and checking using the Sieve of Eratosthenes. It does not require to iterate through all prime numbers after generation, which optimizes the calculation further.

Here’s an example:

def check_prime_sum(n):
    sieve = [True] * (n+1)
    for p in range(2, n//2 + 1):
        if sieve[p]:
            complement = n - p
            if complement < len(sieve) and sieve[complement]:
                return True, (p, complement)
            for i in range(p*2, n+1, p):
                sieve[i] = False
    return False, ()

# Check for the number 17
print(check_prime_sum(17))

Output: (True, (3, 14))

This function works by initializing a sieve list to mark non-primes. The check is performed simultaneously as the sieve list gets updated, which quickly confirms or denies the possibility of expressing the input prime as a sum of two primes.

Bonus One-Liner Method 5: Functional Approach with itertools

Python’s itertools and a functional approach provide a compact one-liner solution. This method is elegant and utilizes powerful Python features, but readability might be sacrificed for compactness and it may not be as efficient due to the combinatorial nature.

Here’s an example:

import itertools

# One-liner to check the prime sum
check_prime_sum = lambda n: any(is_prime(a) and is_prime(n-a) for a in range(2, n))

# Utilizing the existing is_prime function.
# Check for the number 17
print(check_prime_sum(17))

Output: True

The one-liner employs a lambda function with a generator expression that iterates through possible pairs using itertools and checks if each pair are both prime numbers that sum to the input number.

Summary/Discussion

  • Method 1: Sieve of Eratosthenes. Efficient for large numbers, pre-generates all primes. Poor performance for smaller numbers due to overhead.
  • Method 2: Optimized Pairwise Check. More memory-efficient and faster for large numbers, as primes are generated on-the-fly. Might be slower for small numbers due to repeated is_prime checks.
  • Method 3: Hashing Based Technique. Reduces redundancy in prime checks, faster for repeated usage. Requires additional memory to maintain a hash set.
  • Method 4: Simultaneous Sieve and Check. Offers optimization by avoiding post-generation iteration. It could have increased complexity and harder to understand for new programmers.
  • Method 5: Functional Approach with itertools. Compact one-liner potentially sacrificing efficiency for discriveness, best for when readability or performance are of lesser concern.