Express a Number as the Sum of Two Primes

74
0

Given an integer n where (2 ≤ n ≤ 10⁶), return true if two prime numbers add up to n; otherwise, return false.

Example 1

Input: n = 28

Output: true

Explanation: 28 = 5 + 23, and both 5 and 23 are prime numbers.

Example 2

Input: n = 27

Output: false

Explanation: No two prime numbers add up to 27.

Brute Force Approach

A prime number is greater than 1 and has no divisors other than 1 and itself. Because the smallest prime number is 2, the smallest possible sum of two prime numbers is 2 + 2 = 4, meaning any number smaller than 4 can never be formed. For any valid target n, once the first number of a pair is chosen, the second number is automatically fixed as n minus that first number, so the task reduces to checking whether both numbers in the pair are prime.

Except for 2, all prime numbers are odd. Adding two odd numbers always produces an even sum, so an odd sum can only be formed by adding one even number and one odd number. Since 2 is the only even prime, an odd n can only be split into 2 and n - 2. This means an odd n requires only a single check: whether n - 2 is prime.

For an even n, multiple pairs are possible, so candidate values for the first number can be tested starting from 2. Checking the first number only up to n / 2 is sufficient because going past the halfway point simply repeats the same pairs in reverse order (for example, for n = 10, checking 3 + 7 also covers 7 + 3).

Algorithm

  • If n is less than 4, return false immediately, since the smallest sum of two primes is 2 + 2 = 4.

  • If n is odd, check only the pair 2 and n - 2; return true if n - 2 is prime, and false otherwise.

  • If n is even, test each candidate first number from 2 up to n / 2, pairing it with n minus that first number.

  • For each candidate pair, check whether both the first number and the second number are prime, and return true as soon as such a pair is found.

  • If all candidates up to n / 2 are tested and no pair has both numbers prime, return false.

To check whether a number is prime, return false for any number less than 2, and otherwise test possible divisors from 2 up to the square root of the number, since any larger divisor would already have a matching smaller factor below the square root.

Dry Run

Expressing a number as the sum of two primes - Brute

Expressing a number as the sum of two primes - Brute

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks whether a number is prime.
bool isPrime(int value) {
if (value < 2) {
return false;
}
// The only even prime number is 2.
if (value % 2 == 0) {
return value == 2;
}
// For an odd number, only odd divisors need to be checked.
for (int divisor = 3; divisor * divisor <= value; divisor += 2) {
if (value % divisor == 0) {
return false;
}
}
return true;
}
public:
// Returns whether n is the sum of two prime numbers.
bool is_sum_of_two_primes(int n) {
// The smallest possible sum is 2 + 2 = 4.
if (n < 4) {
return false;
}
// An odd sum must contain the only even prime, 2.
if (n % 2 != 0) {
return isPrime(n - 2);
}
// Checking up to n / 2 avoids repeating reversed pairs.
for (int first = 2; first <= n / 2; first++) {
int second = n - first;
if (isPrime(first) && isPrime(second)) {
return true;
}
}
// No pair of primes adds up to n.
return false;
}
};
// Driver code
int main() {
int n = 28;
// Create an instance of class Solution.
Solution sol;
// Print the result as true or false.
cout << boolalpha << sol.is_sum_of_two_primes(n) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N√N) as an upper bound for even inputs, since at most N / 2 candidate pairs are considered and each prime check takes O(√N) time. Odd inputs require only one prime check, taking O(√N) time.

Space Complexity: O(1) auxiliary space because only a fixed number of variables are used.

Optimal Approach

The idea is to first find all prime numbers up to n, then look for two of them whose sum is n. Having the primes ready means their divisibility does not need to be checked again for every possible pair.

The Sieve of Eratosthenes finds these primes by crossing out numbers that cannot be prime. 0 and 1 are excluded, because a prime number must be greater than 1 and have exactly two positive divisors: 1 and itself.

Start with the numbers from 2 to n. Keep 2, but cross out its larger multiples. These multiples have 2 as a divisor besides 1 and themselves, so they cannot be prime. Then take the next number that has not been crossed out and remove its larger multiples for the same reason. The numbers that remain are the primes.

Once the primes are known, choose a prime and subtract it from n. The difference is the only number that can join that prime to give the required sum. If this difference is also prime, a valid pair has been found. Otherwise, try another prime.

Only one valid pair is needed. The two primes may also be equal. If no prime has a prime partner that completes the sum, the number cannot be expressed as the sum of two primes.

Algorithm

  • If n < 4, return false, because the smallest possible sum is 2 + 2.

  • Create a list of prime marks from 0 to n. Mark 0 and 1 as not prime.

  • Starting from 2, take each number p that is still marked as prime.

  • Mark its multiples as not prime, starting from p × p. Smaller multiples that needed removing were already handled by smaller primes.

  • Stop this marking process when p × p > n. The prime list is now ready.

  • Try each first number from 2 through n / 2. Its partner is n - first.

  • Return true if both numbers are marked as prime. If no pair works, return false.

Dry Run

Express a number as the sum of two primes - Optimal

Express a number as the sum of two primes - Optimal

Solution

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns whether n can be written as the sum of two primes.
bool is_sum_of_two_primes(int n) {
// The smallest possible sum is 2 + 2.
if (n < 4) {
return false;
}
vector<bool> isPrime(n + 1, true);
isPrime[0] = isPrime[1] = false;
// Mark multiples of each prime as not prime.
for (int p = 2; p * p <= n; p++) {
if (isPrime[p]) {
// Smaller composite multiples were already marked.
for (int multiple = p * p;
multiple <= n;
multiple += p) {
isPrime[multiple] = false;
}
}
}
// Check each pair once, including pairs with equal primes.
for (int first = 2; first <= n / 2; first++) {
int second = n - first;
if (isPrime[first] && isPrime[second]) {
return true;
}
}
return false;
}
};
// Driver code
int main() {
int n = 28;
// Create an instance of Solution.
Solution sol;
cout << boolalpha << sol.is_sum_of_two_primes(n) << '\n';
return 0;
}

Complexity Analysis

Time Complexity: O(N log(log N)). Building the sieve takes O(N log(log N)) time, and checking the pairs takes at most O(N) time.

Space Complexity: O(N) auxiliary space for the list that stores whether each number is prime.

Interview follow-up Questions

Yes. The two primes do not need to be different. For example, 4 = 2 + 2 and 10 = 5 + 5 are valid.

MathsTCS NQT

Read Similar Blogs

Comments0