Given an integer N, the task is to find the number of distinct prime triplets from the range [1, N] having the sum of the first two numbers equal to the third number.
Examples:
Input: N = 7
Output: 2
Explanation: All valid triplets are (2, 3, 5) and (2, 5, 7). Therefore, the required output is 2.Input: N = 4
Output: 0
Approach: The idea is to use Sieve of Eratosthenes. Follow the steps below to solve the problem:
- Initialize an array, say prime[], to mark all the prime numbers up to N using Sieve of Eratosthenes.
- Initialize an array, say cntTriplet[], to store the count of prime triplets upto N which satisfies the above-mentioned condition.
- Traverse the array cntTriplet[] over the indices [3, N] and check for the following conditions:
- If prime[i] and prime[i – 2] are prime numbers, then update the cntTriplet[i] by 1.
- Otherwise, assign cntTriplet[i] = cntTriplet[i – 1].
- Finally, print the value of cntTriplet[N].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;#define MAX 1000001// Boolean array to// mark prime numbersbool prime[MAX];// To count the prime triplets// having the sum of the first two// numbers equal to the third elementint cntTriplet[MAX];// Function to count prime triplets// having sum of the first two elements// equal to the third elementvoid primeTriplet(long N){ // Sieve of Eratosthenes memset(prime, true, sizeof(prime)); prime[0] = prime[1] = false; for (int i = 2; i * i <= N; i++) { if (prime[i]) { for (int j = i * i; j <= N; j += i) { prime[j] = false; } } } for (int i = 3; i <= N; i++) { // Checks for the prime numbers // having difference equal to2 if (prime[i] && prime[i - 2]) { // Update count of triplets cntTriplet[i] = cntTriplet[i - 1] + 1; } else { cntTriplet[i] = cntTriplet[i - 1]; } } // Print the answer cout << cntTriplet[N];}// Driver Codeint main(){ long N = 7; primeTriplet(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;class GFG{static int MAX = 1000001;// Boolean array to// mark prime numbersstatic boolean[] prime = new boolean[MAX];// To count the prime triplets// having the sum of the first two// numbers equal to the third elementstatic int[] cntTriplet = new int[MAX];// Function to count prime triplets// having sum of the first two elements// equal to the third elementstatic void primeTriplet(int N){ // Sieve of Eratosthenes Arrays.fill(prime, true); prime[0] = prime[1] = false; for (int i = 2; i * i <= N; i++) { if (prime[i]) { for (int j = i * i; j <= N; j += i) { prime[j] = false; } } } for (int i = 3; i <= N; i++) { // Checks for the prime numbers // having difference equal to2 if (prime[i] && prime[i - 2]) { // Update count of triplets cntTriplet[i] = cntTriplet[i - 1] + 1; } else { cntTriplet[i] = cntTriplet[i - 1]; } } // Print the answer System.out.println(cntTriplet[N]);}// Driver Codepublic static void main(String[] args){ int N = 7; primeTriplet(N);}}// This code is contributed by susmitakundugoaldagna. |
Python3
# Python program for the above approach# Function to count prime triplets# having sum of the first two elements# equal to the third elementdef primeTriplet( N): # Sieve of Eratosthenes # Boolean array to # mark prime numbers prime = [True for i in range(1000001)] # To count the prime triplets # having the sum of the first two # numbers equal to the third element cntTriplet = [ 0 for i in range(1000001)] prime[0] = prime[1] = False i = 2 while i * i <= N: if (prime[i]): j = i * i while j <= N: prime[j] = False j += i i += 1 for i in range(3, N + 1): # Checks for the prime numbers # having difference equal to2 if (prime[i] and prime[i - 2]): # Update count of triplets cntTriplet[i] = cntTriplet[i - 1] + 1 else: cntTriplet[i] = cntTriplet[i - 1] # Print the answer print(cntTriplet[N])# Driver CodeN = 7primeTriplet(N)# This code is contributed by rohitsingh07052 |
C#
// C# Program to implement// the above approachusing System;class GFG {static int MAX = 1000001; // Boolean array to// mark prime numbersstatic bool[] prime = new bool[MAX]; // To count the prime triplets// having the sum of the first two// numbers equal to the third elementstatic int[] cntTriplet = new int[MAX]; // Function to count prime triplets// having sum of the first two elements// equal to the third elementstatic void primeTriplet(int N){ // Sieve of Eratosthenes for(int i = 0; i <= N; i++) { prime[i] = true; } prime[0] = prime[1] = false; for (int i = 2; i * i <= N; i++) { if (prime[i]) { for (int j = i * i; j <= N; j += i) { prime[j] = false; } } } for (int i = 3; i <= N; i++) { // Checks for the prime numbers // having difference equal to2 if (prime[i] && prime[i - 2]) { // Update count of triplets cntTriplet[i] = cntTriplet[i - 1] + 1; } else { cntTriplet[i] = cntTriplet[i - 1]; } } // Print the answer Console.WriteLine(cntTriplet[N]);}// Driver Codepublic static void Main(String[] args) { int N = 7; primeTriplet(N);}}// This code is contributed by splevel62. |
Javascript
<script>// Javascript program for the above approachlet MAX = 1000001// Boolean array to// mark prime numberslet prime = new Array(MAX).fill(true);// To count the prime triplets// having the sum of the first two// numbers equal to the third elementlet cntTriplet = new Array(MAX).fill(0);// Function to count prime triplets// having sum of the first two elements// equal to the third elementfunction primeTriplet(N){ prime[0] = false; prime[1] = false; for (let i = 2; i * i <= N; i++) { if (prime[i]) { for (let j = i * i; j <= N; j += i) { prime[j] = false; } } } for (let i = 3; i <= N; i++) { // Checks for the prime numbers // having difference equal to2 if (prime[i] && prime[i - 2]) { // Update count of triplets cntTriplet[i] = cntTriplet[i - 1] + 1; } else { cntTriplet[i] = cntTriplet[i - 1]; } } // Print the answer document.write(cntTriplet[N]);}// Driver Codelet N = 7;primeTriplet(N);// This code is contributed by _saurabh_jaiswal</script> |
Output:
2
Time Complexity: O(N * log(log(N)))
Auxiliary Space: O(MAX)
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!
