Count of primes below N which can be expressed as the sum of two primes
Given an integer N, the task is to find the count of all the primes below N which can be expressed as the sum of two primes.
Examples:
Input: N = 6
Output: 1
5 is the only such prime below 6.
2 + 3 = 5.
Input: N = 11
Output: 2
Approach: Create an array prime[] where prime[i] will store whether i is prime or not using Sieve of Eratosthenes. Now for every prime from the range [1, N – 1], check whether it can be expressed as the sum of two primes using the approach discussed here.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; const int MAX = 100005; bool prime[MAX]; // Function for Sieve of Eratosthenes void SieveOfEratosthenes() { memset (prime, true , sizeof (prime)); // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p <= MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * 2; i <= MAX; i += p) prime[i] = false ; } } } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes int countPrimes( int n) { SieveOfEratosthenes(); // To store the required count int cnt = 0; for ( int i = 2; i < n; i++) { // If the integer is prime and it // can be expressed as the sum of // 2 and a prime number if (prime[i] && prime[i - 2]) cnt++; } return cnt; } // Driver code int main() { int n = 11; cout << countPrimes(n); return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 100005 ; static boolean []prime = new boolean [MAX]; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes() { for ( int i = 0 ; i < MAX; i++) prime[i] = true ; // false here indicates // that it is not prime prime[ 0 ] = false ; prime[ 1 ] = false ; for ( int p = 2 ; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * 2 ; i < MAX; i += p) prime[i] = false ; } } } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes static int countPrimes( int n) { SieveOfEratosthenes(); // To store the required count int cnt = 0 ; for ( int i = 2 ; i < n; i++) { // If the integer is prime and it // can be expressed as the sum of // 2 and a prime number if (prime[i] && prime[i - 2 ]) cnt++; } return cnt; } // Driver code public static void main(String[] args) { int n = 11 ; System.out.print(countPrimes(n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach MAX = 100005 prime = [ True for i in range ( MAX )] # Function for Sieve of Eratosthenes def SieveOfEratosthenes(): # False here indicates # that it is not prime prime[ 0 ] = False prime[ 1 ] = False for p in range ( MAX ): if (p * p > MAX ): break # If prime[p] is not changed, # then it is a prime if (prime[p]): # Update all multiples of p, # set them to non-prime for i in range ( 2 * p, MAX , p): prime[i] = False # Function to return the count of primes # less than or equal to n which can be # expressed as the sum of two primes def countPrimes(n): SieveOfEratosthenes() # To store the required count cnt = 0 for i in range ( 2 , n): # If the integer is prime and it # can be expressed as the sum of # 2 and a prime number if (prime[i] and prime[i - 2 ]): cnt + = 1 return cnt # Driver code n = 11 print (countPrimes(n)) # This code is contributed by Mohit Kumar |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 100005; static bool []prime = new bool [MAX]; // Function for Sieve of Eratosthenes static void SieveOfEratosthenes() { for ( int i = 0; i < MAX; i++) prime[i] = true ; // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for ( int p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for ( int i = p * 2; i < MAX; i += p) prime[i] = false ; } } } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes static int countPrimes( int n) { SieveOfEratosthenes(); // To store the required count int cnt = 0; for ( int i = 2; i < n; i++) { // If the integer is prime and it // can be expressed as the sum of // 2 and a prime number if (prime[i] && prime[i - 2]) cnt++; } return cnt; } // Driver code public static void Main(String[] args) { int n = 11; Console.Write(countPrimes(n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript implementation of the approach var MAX = 100005; var prime = new Array(MAX).fill( false ); // Function for Sieve of Eratosthenes function SieveOfEratosthenes() { for (i = 0; i < MAX; i++) prime[i] = true ; // false here indicates // that it is not prime prime[0] = false ; prime[1] = false ; for (p = 2; p * p < MAX; p++) { // If prime[p] is not changed, // then it is a prime if (prime[p]) { // Update all multiples of p, // set them to non-prime for (i = p * 2; i < MAX; i += p) prime[i] = false ; } } } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes function countPrimes(n) { SieveOfEratosthenes(); // To store the required count var cnt = 0; for (i = 2; i < n; i++) { // If the integer is prime and it // can be expressed as the sum of // 2 and a prime number if (prime[i] && prime[i - 2]) cnt++; } return cnt; } // Driver code var n = 11; document.write(countPrimes(n)); // This code is contributed by todaysgaurav </script> |
2
Time Complexity: O(N*log(√N)), where N represents the maximum integer
Auxiliary Space: O(N), where N represents the maximum integer
Approach 2: Constant Space:
- The Above Approach uses an array prime of size MAX to keep track of whether each number is prime or not. This array takes up MAX * sizeof(bool) bytes of memory.
- To implement the same logic in constant space, we can that checks whether a given number is prime or not. This function takes an integer n as input and returns true if n is prime, and false otherwise.
- The isPrime function uses trial division to check whether n is divisible by any integer between 2 and sqrt(n). Since we only need to check up to sqrt(n), the amount of memory used by the function is constant.
Here’s the updated code with the constant space:
C++
#include <cmath> #include <iostream> using namespace std; // Function to check if a number is prime bool isPrime( int n) { if (n <= 1) { return false ; } for ( int i = 2; i <= sqrt (n); i++) { if (n % i == 0) { return false ; } } return true ; } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes int countPrimes( int n) { int cnt = 0; for ( int i = 2; i < n; i++) { if (isPrime(i) && isPrime(i - 2)) { cnt++; } } return cnt; } // Driver code int main() { int n = 11; cout << countPrimes(n) << endl; return 0; } |
Java
import java.util.*; public class GFG { // Function to check if a number is prime static boolean isPrime( int n) { if (n <= 1 ) { return false ; } // Loop from 2 to the square root of n to check for // divisibility for ( int i = 2 ; i <= Math.sqrt(n); i++) { if (n % i == 0 ) { return false ; } } return true ; } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes static int countPrimes( int n) { int cnt = 0 ; // Loop from 2 to n-1 to check each number for ( int i = 2 ; i < n; i++) { // Check if both i and (i-2) are prime if (isPrime(i) && isPrime(i - 2 )) { cnt++; } } return cnt; } // Driver code public static void main(String[] args) { int n = 11 ; // Call the countPrimes function and print the // result System.out.println(countPrimes(n)); } } |
Python
import math # Function to check if a number is prime def is_prime(n): if n < = 1 : return False for i in range ( 2 , int (math.sqrt(n)) + 1 ): if n % i = = 0 : return False return True # Function to return the count of primes # less than or equal to n which can be # expressed as the sum of two primes def count_primes(n): count = 0 for i in range ( 2 , n): if is_prime(i) and is_prime(i - 2 ): count + = 1 return count # Driver code if __name__ = = "__main__" : n = 11 print (count_primes(n)) # sinudp5vi |
C#
using System; class GFG { // Function to check if a number is prime static bool IsPrime( int n) { if (n <= 1) { return false ; // 1 and all numbers less than or // equal to 1 are not prime } for ( int i = 2; i <= Math.Sqrt(n); i++) { if (n % i == 0) { return false ; // If the number is divisible // by any number between 2 and // its square root, it's not // prime } } return true ; // If the number passes all the checks, // it is prime } // Function to count the number of twin primes less than // n static int CountPrimes( int n) { int cnt = 0; // Initialize a counter to count the // twin primes for ( int i = 2; i < n; i++) { if (IsPrime(i) && IsPrime(i - 2)) { cnt++; // Increment the counter if both i // and (i-2) are prime (twin primes) } } return cnt; // Return the count of twin primes } static void Main( string [] args) { int n = 11; // Find the number of twin primes less // than 11 Console.WriteLine( CountPrimes(n)); // Print the result } } |
Javascript
// Function to check if a number is prime function isPrime(n) { if (n <= 1) { return false ; } // Loop from 2 to the square root of n to check for divisibility for (let i = 2; i <= Math.sqrt(n); i++) { if (n % i === 0) { return false ; } } return true ; } // Function to return the count of primes // less than or equal to n which can be // expressed as the sum of two primes function countPrimes(n) { let cnt = 0; // Loop from 2 to n-1 to check each number for (let i = 2; i < n; i++) { // Check if both i and (i-2) are prime if (isPrime(i) && isPrime(i - 2)) { cnt++; } } return cnt; } // Driver code const n = 11; // Call the countPrimes function and print the result console.log(countPrimes(n)); |
2
Time Complexity: O(n * sqrt(n))
Auxiliary Space: O(1)
Contact Us