Problem
Given a positive number N, print the count of prime numbers from 1 to N that can be written as a sum of two prime numbers.
|
Prime numbers are the numbers greater than 1 and have exactly two factors, 1 and themselves. For example, 2, 3, 5, 7, etc., are the prime numbers. |
Input: An integer N.
Output: An integer.
The questions you should ask the interviewer:
- What is the constraint on N?
For example,
|
1. Input: N = 7. Output: 2. Explanation: 5 and 7 are the prime numbers over the range [1, 7] that can be represented as a sum of two prime numbers, i.e., 5 = 2 + 3, and 7 = 2 + 5, where 2, 3, 5, and 7 are all primes.
2. Input: N = 15. Output: 3. Explanation: 5(2 + 3), 7(2 + 5), and 13(2 + 11) are the prime numbers over the range [1, 15] that can be represented as a sum of two prime numbers. |
Recommended: Please try to solve it yourself before moving on to the solution.
Solution
Naive Approach:
One basic approach would be to consider all pairs (i, j) over the range [1, N] and if i, j, and (i+j) are prime numbers and (i + j) lies in the range [1, N], increment the count. After checking for all possible pairs, print the count.
Time Complexity: O(N3). One for loop is used for i in the range [1, N], one for loop for j in the range [1, N], and one loop in the range [1, N] is used to check if i, j, and i+j are prime numbers or not. Hence O(N3) time.
Space Complexity: O(1).
Let's try to improve time complexity.
Efficient Approach:
Some observations:
- 2 is the only even prime number. All the other prime numbers are odd.
- An odd number is always the sum of an even and an odd number.
- It is impossible to represent a prime number(which is odd) as a sum of two odd prime numbers. Therefore to represent a prime number as a sum of two prime numbers, one prime number must be even, which is 2 only.
- So a prime number X can be represented as a sum of two prime numbers (2 + (X-2)) if X-2 is also prime.
Algorithm:
- Initialize a dp array of size N+1 where dp[i] will represent the count of prime numbers from a range of [1, i] that can be described as a sum of two prime numbers.
- Initialize an array prime of size N+1, and add all the prime numbers till N using the Sieve Of Eratosthenes.
-
Loop over [2, N] and do the following:
- Add previous values in dp[i]: dp[i] = dp[i-1].
- Increment dp[i] by 1 if i and i-2 are prime numbers as prime number i can be represented as (2 + ( i-2 )).
C++
|
#include <bits/stdc++.h> using namespace std; // Sieve of Eratosthenes to store prime numbers. void SieveOfEratosthenes(vector<bool> &prime, int n) { // set 0 and 1 as non prime. prime[0] = 0; prime[1] = 0; for (int i = 2; i * i <= n; i++) { // If p is a prime number. if (prime[i]) { // Set all multiples of p as a non-prime number. for (int m = i * i; m <= n; m += i) { prime[m] = false; } } } } // Function to count the required prime numbers. int PrimeNum(int n) { // Stores all the prime numbers. vector<bool> prime(n+1, 1); SieveOfEratosthenes(prime, n); // Create a dp array. vector<int> dp(n+1, 0); // Iterate over the range of [2, N]. for (int i = 2; i <= n; i++) { // Update dp[i] by adding the previous count value. dp[i] = dp[i - 1]; // Increment dp[i] by 1 if i and (i - 2) are prime numbers. if (prime[i] && prime[i - 2] ) { dp[i] = dp[i] + 1; } } return dp[n]; } int main() { int N = 15; cout<<PrimeNum(N); return 0; } |
Input: N = 15.
Output: 3.
Time Complexity: O(N * log(log(N))).
Space Complexity: O(N). Extra space is used by the arrays: prime and dp.
Also see, Euclid GCD Algorithm
40+ registered 
