Given a number N. The task is to count the number of prime numbers from 2 to N that can be expressed as a sum of two consecutive primes and 1.
Examples:
Input: N = 27
Output: 2
13 = 5 + 7 + 1 and 19 = 7 + 11 + 1 are the required prime numbers.
Input: N = 34
Output: 3
13 = 5 + 7 + 1, 19 = 7 + 11 + 1 and 31 = 13 + 17 + 1.
Approach: An efficient approach is to find all the primes numbers up to N using Sieve of Eratosthenes and place all the prime numbers in a vector. Now, run a simple loop and add two consecutive primes and 1 then check if this sum is also a prime. If it is then increment the count.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;#define N 100005// To check if a number is prime or notbool isprime[N];// To store possible numbersbool can[N];// Function to return all prime numbersvector<int> SieveOfEratosthenes(){ memset(isprime, true, sizeof(isprime)); for (int p = 2; p * p < N; p++) { // If prime[p] is not changed, then it is a prime if (isprime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < N; i += p) isprime[i] = false; } } vector<int> primes; for (int i = 2; i < N; i++) if (isprime[i]) primes.push_back(i); return primes;}// Function to count all possible prime numbers that can be// expressed as the sum of two consecutive primes and oneint Prime_Numbers(int n){ vector<int> primes = SieveOfEratosthenes(); // All possible prime numbers below N for (int i = 0; i < (int)(primes.size()) - 1; i++) if (primes[i] + primes[i + 1] + 1 < N) can[primes[i] + primes[i + 1] + 1] = true; int ans = 0; for (int i = 2; i <= n; i++) { if (can[i] and isprime[i]) { ans++; } } return ans;}// Driver codeint main(){ int n = 50; cout << Prime_Numbers(n); return 0;} |
Java
// Java implementation of the approach import java.util.*;class GfG {static int N = 100005; // To check if a number is prime or not static boolean isprime[] = new boolean[N]; // To store possible numbers static boolean can[] = new boolean[N]; // Function to return all prime numbers static ArrayList<Integer>SieveOfEratosthenes() { for(int a = 0 ; a < isprime.length; a++) { isprime[a] = true; } for (int p = 2; p * p < N; p++) { // If prime[p] is not changed, then it is a prime if (isprime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < N; i += p) isprime[i] = false; } } ArrayList<Integer> primes = new ArrayList<Integer> (); for (int i = 2; i < N; i++) if (isprime[i]) primes.add(i); return primes; } // Function to count all possible prime numbers that can be // expressed as the sum of two consecutive primes and one static int Prime_Numbers(int n) { ArrayList<Integer> primes = SieveOfEratosthenes(); // All possible prime numbers below N for (int i = 0; i < (int)(primes.size()) - 1; i++) if (primes.get(i) + primes.get(i + 1) + 1 < N) can[primes.get(i) + primes.get(i + 1) + 1] = true; int ans = 0; for (int i = 2; i <= n; i++) { if (can[i] && isprime[i] == true) { ans++; } } return ans; } // Driver code public static void main(String[] args) { int n = 50; System.out.println(Prime_Numbers(n)); }} // This code is contributed by // Prerna Saini. |
Python3
# Python3 implementation of the approach from math import sqrt;N = 100005;# To check if a number is prime or not isprime = [True] * N; # To store possible numbers can = [False] * N; # Function to return all prime numbers def SieveOfEratosthenes() : for p in range(2, int(sqrt(N)) + 1) : # If prime[p] is not changed, # then it is a prime if (isprime[p] == True) : # Update all multiples of p greater # than or equal to the square of it # numbers which are multiple of p and are # less than p^2 are already been marked. for i in range(p * p, N , p) : isprime[i] = False; primes = []; for i in range(2, N) : if (isprime[i]): primes.append(i); return primes; # Function to count all possible prime numbers# that can be expressed as the sum of two # consecutive primes and one def Prime_Numbers(n) : primes = SieveOfEratosthenes(); # All possible prime numbers below N for i in range(len(primes) - 1) : if (primes[i] + primes[i + 1] + 1 < N) : can[primes[i] + primes[i + 1] + 1] = True; ans = 0; for i in range(2, n + 1) : if (can[i] and isprime[i]) : ans += 1; return ans; # Driver code if __name__ == "__main__" : n = 50; print(Prime_Numbers(n)); # This code is contributed by Ryuga |
C#
// C# implementation of the approach using System;using System.Collections;class GfG {static int N = 100005; // To check if a number is prime or not static bool[] isprime = new bool[N]; // To store possible numbers static bool[] can = new bool[N]; // Function to return all prime numbers static ArrayList SieveOfEratosthenes() { for(int a = 0 ; a < N; a++) { isprime[a] = true; } for (int p = 2; p * p < N; p++) { // If prime[p] is not changed, then it is a prime if (isprime[p] == true) { // Update all multiples of p greater than or // equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (int i = p * p; i < N; i += p) isprime[i] = false; } } ArrayList primes = new ArrayList(); for (int i = 2; i < N; i++) if (isprime[i]) primes.Add(i); return primes; } // Function to count all possible prime numbers that can be // expressed as the sum of two consecutive primes and one static int Prime_Numbers(int n) { ArrayList primes = SieveOfEratosthenes(); // All possible prime numbers below N for (int i = 0; i < primes.Count - 1; i++) if ((int)primes[i] + (int)primes[i + 1] + 1 < N) can[(int)primes[i] + (int)primes[i + 1] + 1] = true; int ans = 0; for (int i = 2; i <= n; i++) { if (can[i] && isprime[i] == true) { ans++; } } return ans; } // Driver code static void Main() { int n = 50; Console.WriteLine(Prime_Numbers(n)); }} // This code is contributed by mits |
PHP
<?php// PHP implementation of the approach$N = 10005;// To check if a number is prime or not$isprime = array_fill(0, $N, true);// To store possible numbers$can = array_fill(0, $N, false);// Function to return all prime numbersfunction SieveOfEratosthenes(){ global $N, $isprime; for ($p = 2; $p * $p < $N; $p++) { // If prime[p] is not changed, // then it is a prime if ($isprime[$p] == true) { // Update all multiples of p greater // than or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for ($i = $p * $p; $i < $N; $i += $p) $isprime[$i] = false; } } $primes = array(); for ($i = 2; $i < $N; $i++) if ($isprime[$i]) array_push($primes, $i); return $primes;}// Function to count all possible prime numbers // that can be expressed as the sum of two // consecutive primes and onefunction Prime_Numbers($n){ global $N, $can, $isprime; $primes = SieveOfEratosthenes(); // All possible prime numbers below N for ($i = 0; $i < count($primes) - 1; $i++) if ($primes[$i] + $primes[$i + 1] + 1 < $N) $can[$primes[$i] + $primes[$i + 1] + 1] = true; $ans = 0; for ($i = 2; $i <= $n; $i++) { if ($can[$i] and $isprime[$i]) { $ans++; } } return $ans;}// Driver code$n = 50;echo Prime_Numbers($n);// This code is contributed by mits?> |
Javascript
<script>// JavaScript implementation of the approachlet N = 10005;// To check if a number is prime or notlet isprime = new Array(N).fill(true);// To store possible numberslet can = new Array(N).fill(false);// Function to return all prime numbersfunction SieveOfEratosthenes(){ for (let p = 2; p * p < N; p++) { // If prime[p] is not changed, // then it is a prime if (isprime[p] == true) { // Update all multiples of p greater // than or equal to the square of it // numbers which are multiple of p and are // less than p^2 are already been marked. for (let i = p * p; i < N; i += p) isprime[i] = false; } } let primes = new Array(); for (let i = 2; i < N; i++) if (isprime[i]) primes.push(i); return primes;}// Function to count all possible prime numbers// that can be expressed as the sum of two// consecutive primes and onefunction Prime_Numbers(n){ let primes = SieveOfEratosthenes(); // All possible prime numbers below N for (let i = 0; i < primes.length - 1; i++) if (primes[i] + primes[i + 1] + 1 < N) can[primes[i] + primes[i + 1] + 1] = true; let ans = 0; for (let i = 2; i <= n; i++) { if (can[i] && isprime[i]) { ans++; } } return ans;}// Driver codelet n = 50;document.write(Prime_Numbers(n));// This code is contributed by gfgking</script> |
Output:
5
Time Complexity: O(N log (log N))
Auxiliary Space: O(100005)
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!
