Write a java program to check if any number given as input is the sum of 2 prime numbers.
Question Explanation
The task at hand is to determine if a given number can be expressed as the sum of two prime numbers. This is an interesting problem because it combines fundamental concepts of number theory with practical programming skills. Interviewers often ask this question to assess a candidate's understanding of primes, algorithms, and efficient coding practices. The Goldbach Conjecture suggests that every even integer greater than two can be expressed as the sum of two primes, making this problem not only theoretically significant but also relevant in algorithm design. By solving this, candidates can demonstrate their ability to think critically, utilize appropriate data structures, and optimize code for performance. Common pitfalls include failing to account for edge cases, such as testing negative numbers or the number 1, which cannot be expressed as the sum of two primes. This question also opens up discussions about time complexity and space complexity, which are crucial in software engineering. Ultimately, the ability to successfully implement such a solution showcases a candidate's proficiency in Java programming and their understanding of fundamental mathematical concepts.
Sample Answers
Example 1: Basic Approach with Nested Loops
To solve the problem, we'll use a nested loop approach to check each pair of prime numbers. The steps are as follows:
- Generate prime numbers up to the given number using the Sieve of Eratosthenes.
- Use two nested loops to iterate through the list of primes.
- Check if the sum of each pair equals the input number.
- If a pair is found, return true; otherwise, return false after all pairs are checked.
Here’s the Java code implementation:
import java.util.*;
public class PrimeSumChecker {
public static boolean isSumOfTwoPrimes(int num) {
if (num < 2) return false;
List<Integer> primes = generatePrimes(num);
for (int i = 0; i < primes.size(); i++) {
for (int j = i; j < primes.size(); j++) {
if (primes.get(i) + primes.get(j) == num) {
return true;
}
}
}
return false;
}
private static List<Integer> generatePrimes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primes.add(i);
}
return primes;
}
}
Time Complexity: O(n^2) for nested loops, where n is the number of primes. Space Complexity: O(n) for storing primes.
Example 2: Optimized Approach with Hashing
In this example, we can optimize our approach using a HashSet to store prime numbers. This allows for faster lookups when checking for the complement of each prime. Here’s how:
- Generate all prime numbers up to the given number.
- Store these primes in a HashSet for O(1) access.
- For each prime, check if the difference between the input number and the prime exists in the HashSet.
- If a match is found, return true.
Here’s the optimized Java code:
import java.util.*;
public class PrimeSumChecker {
public static boolean isSumOfTwoPrimes(int num) {
if (num < 2) return false;
Set<Integer> primes = new HashSet<>(generatePrimes(num));
for (int prime : primes) {
if (primes.contains(num - prime)) {
return true;
}
}
return false;
}
private static List<Integer> generatePrimes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primeList = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primeList.add(i);
}
return primeList;
}
}
Time Complexity: O(n) for generating primes and O(m) for checking pairs, where m is the number of primes. Space Complexity: O(n) for the HashSet.
Example 3: Using a Single Loop with Two Pointers
A more efficient approach involves using the two-pointer technique after generating the primes. Here's the process:
- Generate all prime numbers up to the input number.
- Initialize two pointers: one at the start and another at the end of the prime list.
- If the sum of the two primes is equal to the input number, return true. If the sum is less, move the left pointer to the right; if it's more, move the right pointer to the left.
Here’s the Java implementation:
import java.util.*;
public class PrimeSumChecker {
public static boolean isSumOfTwoPrimes(int num) {
if (num < 2) return false;
List<Integer> primes = generatePrimes(num);
int left = 0, right = primes.size() - 1;
while (left <= right) {
int sum = primes.get(left) + primes.get(right);
if (sum == num) return true;
if (sum < num) left++;
else right--;
}
return false;
}
private static List<Integer> generatePrimes(int n) {
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= n; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
}
}
}
List<Integer> primeList = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (isPrime[i]) primeList.add(i);
}
return primeList;
}
}
Time Complexity: O(n) for generating primes and O(m) for the two-pointer search. Space Complexity: O(n) for storing primes.
Keywords
Ready to practice more questions?
Explore our collection of technical interview questions from top companies.
View All Questions