Count prime numbers up to N that can be represented as a sum of two prime numbers

0 0 13 minutes read

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(N³)
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 10⁵, and populate all the prime numbers till 10⁵ 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 Eratosthenes
void 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 numbers
void 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 Code
int main()
{
    int N = 6;
    countPrime(N);
 
    return 0;
}

Java

// Java approach for the above approach
import java.io.*;
public class GFG{
     
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
static 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 numbers
static 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 Code
public 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 Eratosthenes
def 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 numbers
def 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 Code
if __name__ == "__main__":
 
    N = 6
     
    countPrime(N)
     
# This code is contributed by mohit ukasp

C#

// C# program for the above approach
using System;
 
class GFG{
     
// Function to store all prime numbers
// up to N using Sieve of Eratosthenes
static 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 numbers
static 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 code
static 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 Eratosthenes
function 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 numbers
function 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 code
var n = 6;
 
countPrime(n);
 
// This code is contributed by SoumikMondal
 
</script>

Output

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 prime
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 <= 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
void 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 code
int 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 prime
def 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 numbers
def 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 Code
if __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 prime
function 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 numbers
function 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 code
const 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 numbers
countPrime(N);

Output

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 zambiatek!