Given a positive integer N, the task is to find the count of prime numbers less than or equal to N that can be represented as a sum of two prime numbers.
Examples:
Input: N = 6
Output: 1
Explanation:
5 is the only prime number over the range [1, 6] that can be represented as sum of 2 prime numbers i.e., 5 = 2 + 3, where 2, 3 and 5 are all primes.
Therefore, the count is 2.Input: N = 14
Output: 3
Naive Approach: The simplest approach to solve the given problem is to consider all possible pairs (i, j) over the range [1, N] and if i and j are prime numbers and (i + j) lies in the range [1, N] then increment the count of prime numbers. After checking for all possible pairs, print the value of the total count obtained.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized based on the following observation:
- Apart from 2, all the prime numbers are odd
- It is not possible to represent a prime number(which is odd) to be represented as a sum of two odd prime numbers, so one of the two prime numbers should be 2.
- So for a prime number X to be a sum of two prime numbers, X – 2 must also be prime.
Follow the steps below to solve the problem:
- Initialize an array, say prime[] of size 105, and populate all the prime numbers till 105 using the Sieve Of Eratosthenes.
- Initialize an auxiliary array dp[] of the size (N + 1) where dp[i] is the count of prime numbers less than or equal to i that can be represented as a sum of 2 prime numbers.
- Iterate over the range [2, N] using the variable i and perform the following steps:
- Update the value of dp[i – 1] as the sum of dp[i – 1] and dp[i].
- Check if prime[i] and prime[i – 2] is true, then increment the value of dp[i] by 1.
- After completing the above steps, print the value of dp[N] as the resultant count.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to store all prime numbers// up to N using Sieve of Eratosthenesvoid SieveOfEratosthenes( int n, bool prime[]){ // Set 0 and 1 as non-prime prime[0] = 0; prime[1] = 0; for (int p = 2; p * p <= n; p++) { // If p is prime if (prime[p] == true) { // Set all multiples // of p as non-prime for (int i = p * p; i <= n; i += p) { prime[i] = false; } } }}// Function to count prime numbers// up to N that can be represented// as the sum of two prime numbersvoid countPrime(int n){ // Stores all the prime numbers bool prime[n + 1]; memset(prime, true, sizeof(prime)); // Update the prime array SieveOfEratosthenes(n, prime); // Create a dp array of size n + 1 int dp[n + 1]; memset(dp, 0, sizeof(dp)); // Update dp[1] = 0 dp[1] = 0; // Iterate over the range [2, N] for (int i = 2; i <= n; i++) { // Add the previous count value dp[i] += dp[i - 1]; // Increment dp[i] by 1 if i // and (i - 2) are both prime if (prime[i] == 1 && prime[i - 2] == 1) { dp[i]++; } } // Print the result cout << dp[n];}// Driver Codeint main(){ int N = 6; countPrime(N); return 0;} |
Java
// Java approach for the above approachimport java.io.*;public class GFG{ // Function to store all prime numbers// up to N using Sieve of Eratosthenesstatic void SieveOfEratosthenes(int n, boolean prime[]){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p <= n; p++) { // If p is prime if (prime[p] == true) { // Set all multiples // of p as non-prime for(int i = p * p; i <= n; i += p) { prime[i] = false; } } }}// Function to count prime numbers// up to N that can be represented// as the sum of two prime numbersstatic void countPrime(int n){ // Stores all the prime numbers boolean prime[] = new boolean[n + 1]; for(int i = 0; i < prime.length; i++) { prime[i] = true; } // Update the prime array SieveOfEratosthenes(n, prime); // Create a dp array of size n + 1 int dp[] = new int[n + 1]; for(int i = 0; i < dp.length; i++) { dp[i] = 0; } // Update dp[1] = 0 dp[1] = 0; // Iterate over the range [2, N] for(int i = 2; i <= n; i++) { // Add the previous count value dp[i] += dp[i - 1]; // Increment dp[i] by 1 if i // and (i - 2) are both prime if (prime[i] == true && prime[i - 2] == true) { dp[i]++; } } // Print the result System.out.print(dp[n]);}// Driver Codepublic static void main(String[] args){ int N = 6; countPrime(N);}}// This code is contributed by abhinavjain194 |
Python3
# Python3 program for the above approach# Function to store all prime numbers# up to N using Sieve of Eratosthenesdef SieveOfEratosthenes(n, prime): # Set 0 and 1 as non-prime prime[0] = 0 prime[1] = 0 p = 2 while p * p <= n: # If p is prime if (prime[p] == True): # Set all multiples # of p as non-prime for i in range(p * p, n + 1, p): prime[i] = False p += 1# Function to count prime numbers# up to N that can be represented# as the sum of two prime numbersdef countPrime(n): # Stores all the prime numbers prime = [True] * (n + 1) # Update the prime array SieveOfEratosthenes(n, prime) # Create a dp array of size n + 1 dp = [0] * (n + 1) # Update dp[1] = 0 dp[1] = 0 # Iterate over the range [2, N] for i in range(2, n + 1): # Add the previous count value dp[i] += dp[i - 1] # Increment dp[i] by 1 if i # and (i - 2) are both prime if (prime[i] == 1 and prime[i - 2] == 1): dp[i] += 1 # Print the result print(dp[n])# Driver Codeif __name__ == "__main__": N = 6 countPrime(N) # This code is contributed by mohit ukasp |
C#
// C# program for the above approachusing System;class GFG{ // Function to store all prime numbers// up to N using Sieve of Eratosthenesstatic void SieveOfEratosthenes(int n, bool[] prime){ // Set 0 and 1 as non-prime prime[0] = false; prime[1] = false; for(int p = 2; p * p <= n; p++) { // If p is prime if (prime[p] == true) { // Set all multiples // of p as non-prime for(int i = p * p; i <= n; i += p) { prime[i] = false; } } }}// Function to count prime numbers// up to N that can be represented// as the sum of two prime numbersstatic void countPrime(int n){ // Stores all the prime numbers bool[] prime = new bool[n + 1]; for(int i = 0; i < prime.Length; i++) { prime[i] = true; } // Update the prime array SieveOfEratosthenes(n, prime); // Create a dp array of size n + 1 int[] dp = new int[n + 1]; for(int i = 0; i < dp.Length; i++) { dp[i] = 0; } // Update dp[1] = 0 dp[1] = 0; // Iterate over the range [2, N] for(int i = 2; i <= n; i++) { // Add the previous count value dp[i] += dp[i - 1]; // Increment dp[i] by 1 if i // and (i - 2) are both prime if (prime[i] == true && prime[i - 2] == true) { dp[i]++; } } // Print the result Console.Write(dp[n]);}// Driver codestatic void Main(){ int N = 6; countPrime(N);}}// This code is contributed by abhinavjain194 |
Javascript
<script>// Javascript program for the above approach// Function to store all prime numbers// up to N using Sieve of Eratosthenesfunction SieveOfEratosthenes(n, prime){ // Set 0 and 1 as non-prime prime[0] = 0; prime[1] = 0; for(var p = 2; p * p <= n; p++) { // If p is prime if (prime[p] == Boolean(true)) { // Set all multiples // of p as non-prime for(var i = p * p;i <= n; i += p) { prime[i] = Boolean(false); } } }}// Function to count prime numbers// up to N that can be represented// as the sum of two prime numbersfunction countPrime(n){ // Stores all the prime numbers var prime = new Array(n + 1); var x = new Boolean(true); prime.fill(x); // Update the prime array SieveOfEratosthenes(n, prime); // Create a dp array of size n + 1 var dp = new Array(n + 1); dp.fill(0); // Update dp[1] = 0 dp[1] = 0; // Iterate over the range [2, N] for(var i = 2; i <= n; i++) { // Add the previous count value dp[i] += dp[i - 1]; // Increment dp[i] by 1 if i // and (i - 2) are both prime if (prime[i] == Boolean(true) && prime[i - 2] == Boolean(true)) { dp[i]++; } } // Print the result document.write(dp[n]);}// Driver codevar n = 6;countPrime(n);// This code is contributed by SoumikMondal</script> |
Output
1
Time Complexity: O(N * log(log(N)))
Auxiliary Space: O(N)
Approach:
Here is the code of above algorithm:
C++
#include <cmath>#include <iostream>#include <unordered_set>using namespace std;// Function to check if a number is primebool isPrime(int n){ // If the number is less than or equal to // 1, it is not prime if (n <= 1) { return false; } // Loop to check for factors from 2 to the // square root of the number for (int i = 2; i <= sqrt(n); i++) { // If the number is divisible by // i, it is not prime if (n % i == 0) { return false; } } // If no factors found, the number is prime return true;}// Function to count prime numbers up to N that can be// represented as the sum of two prime numbersvoid countPrime(int n){ // Create an unordered set to // store prime numbers unordered_set<int> primes; // Initialize a counter to keep track of // the count of prime numbers that can be // represented as sum of two primes int count = 0; // Loop to iterate from 2 to N for (int i = 2; i <= n; i++) { // Check if i is a prime number if (isPrime(i)) { // Add the prime number i to the set primes.insert(i); // Check if (i-2) is also a prime // number and present in the set if (primes.count(i - 2) > 0) { // If yes, increment the count as // (i-2) + 2 = i, which is a prime // number represented as the sum of // two primes count++; } } } // Output the count of prime numbers that // can be represented as the sum of two primes cout << count << endl;}// Driver codeint main(){ // Define the upper limit N int N = 6; // Call the function to count prime numbers up // to N that can be represented as the sum of // two prime numbers countPrime(N); return 0;} |
Java
import java.util.HashSet;import java.util.Set;public class Main { // Function to check if a number is prime public static boolean isPrime(int n) { // If the number is less than or equal to 1, it is not prime if (n <= 1) { return false; } // Loop to check for factors from 2 to the square root of the number for (int i = 2; i <= Math.sqrt(n); i++) { // If the number is divisible by i, it is not prime if (n % i == 0) { return false; } } // If no factors found, the number is prime return true; } // Function to count prime numbers up to N that can be represented as the sum of two prime numbers public static void countPrime(int n) { // Create a set to store prime numbers Set<Integer> primes = new HashSet<>(); // Initialize a counter to keep track of the count of prime numbers that can be represented as the sum of two primes int count = 0; // Loop to iterate from 2 to N for (int i = 2; i <= n; i++) { // Check if i is a prime number if (isPrime(i)) { // Add the prime number i to the set primes.add(i); // Check if (i-2) is also a prime number and present in the set if (primes.contains(i - 2)) { // If yes, increment the count as (i-2) + 2 = i, which is a prime number represented as the sum of two primes count++; } } } // Output the count of prime numbers that can be represented as the sum of two primes System.out.println(count); } // Driver code public static void main(String[] args) { // Define the upper limit N int N = 6; // Call the function to count prime numbers up to N that can be represented as the sum of two prime numbers countPrime(N); }} |
Python3
# Function to check if a number is primedef isPrime(n): if n <= 1: return False for i in range(2, int(n**0.5) + 1): if n % i == 0: return False return True# Function to count prime numbers# up to N that can be represented# as the sum of two prime numbersdef countPrime(n): primes = set() count = 0 #counts the prime numbers for i in range(2, n+1): if isPrime(i): #check if prime primes.add(i) if (i-2) in primes: count += 1 print(count)# Driver Codeif __name__ == "__main__": N = 6 countPrime(N) |
C#
using System;using System.Collections.Generic;namespace PrimeCount{ class GFG { // Function to check if a number is prime static bool IsPrime(int n) { // If the number is less than or equal to // 1, it is not prime if (n <= 1) { return false; } // Loop to check for factors from 2 to the // square root of the number for (int i = 2; i <= Math.Sqrt(n); i++) { // If the number is divisible by // i, it is not prime if (n % i == 0) { return false; } } // If no factors found, the number is prime return true; } // Function to count prime numbers up to N that can be // represented as the sum of two prime numbers static void CountPrime(int n) { // Create a HashSet to store prime numbers HashSet<int> primes = new HashSet<int>(); // Initialize a counter to keep track of // the count of prime numbers that can be // represented as the sum of two primes int count = 0; // Loop to iterate from 2 to N for (int i = 2; i <= n; i++) { // Check if i is a prime number if (IsPrime(i)) { // Add the prime number i to the set primes.Add(i); // Check if (i-2) is also a prime // number and present in the set if (primes.Contains(i - 2)) { // If yes, increment the count as // (i-2) + 2 = i, which is a prime // number represented as the sum of // two primes count++; } } } // Output the count of prime numbers that // can be represented as the sum of two primes Console.WriteLine(count); } // Driver code static void Main(string[] args) { // Define the upper limit N int N = 6; // Call the function to count prime numbers up // to N that can be represented as the sum of // two prime numbers CountPrime(N); } }} |
Javascript
// Function to check if a number is primefunction isPrime(n) { // If the number is less than or equal to 1, it is not prime if (n <= 1) { return false; } // Loop to check for factors from 2 to the square root of the number for (let i = 2; i <= Math.sqrt(n); i++) { // If the number is divisible by i, it is not prime if (n % i === 0) { return false; } } // If no factors found, the number is prime return true;}// Function to count prime numbers up to N that can be represented as the sum of two prime numbersfunction countPrime(n) { // Create a Set to store prime numbers const primes = new Set(); // Initialize a counter to keep track of the count // of prime numbers that can be represented as the sum of two primes let count = 0; // Loop to iterate from 2 to N for (let i = 2; i <= n; i++) { // Check if i is a prime number if (isPrime(i)) { // Add the prime number i to the Set primes.add(i); // Check if (i-2) is also a prime number and present in the Set if (primes.has(i - 2)) { // If yes, increment the count as (i-2) + 2 = i, which is a prime // number represented as the sum of two primes count++; } } } // Output the count of prime numbers that can be represented as the sum of two primes console.log(count);}// Driver codeconst N = 6; // Define the upper limit N// Call the function to count prime numbers up to N that can be represented// as the sum of two prime numberscountPrime(N); |
Output
1
Time Complexity: O(n^(3/2))
Auxiliary Space: O(sqrt(n))
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
