Contar trillizos primos hasta N que tengan la suma de los dos primeros elementos igual al tercer número

Dado un número entero N , la tarea es encontrar el número de tripletes primos distintos del rango [1, N] que tienen la suma de los dos primeros números igual al tercer número.

Ejemplos:

Entrada: N = 7
Salida: 2
Explicación: Todos los tripletes válidos son (2, 3, 5) y (2, 5, 7). Por lo tanto, la salida requerida es 2.

Entrada: N = 4
Salida: 0

Planteamiento: La idea es utilizar Tamiz de Eratóstenes . Siga los pasos a continuación para resolver el problema:

• Inicialice una array , digamos prime[] , para marcar todos los números primos hasta N usando Sieve of Eratosthenes .
• Inicialice una array , digamos cntTriplet[] , para almacenar el recuento de trillizos primos hasta N que satisfaga la condición mencionada anteriormente.
• Recorra la array cntTriplet[] sobre los índices [3, N] y verifique las siguientes condiciones:
  • Si prime[i] y prime[i – 2] son ​​números primos , actualice cntTriplet[i] en 1 .
  • De lo contrario, asigne cntTriplet[i] = cntTriplet[i – 1] .
• Finalmente, imprima el valor de cntTriplet[N] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000001
 
// Boolean array to
// mark prime numbers
bool prime[MAX];
 
// To count the prime triplets
// having the sum of the first two
// numbers equal to the third element
int cntTriplet[MAX];
 
// Function to count prime triplets
// having sum of the first two elements
// equal to the third element
void 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 Code
int main()
{
    long N = 7;
    primeTriplet(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class GFG{
static int MAX = 1000001;
 
// Boolean array to
// mark prime numbers
static boolean[] prime = new boolean[MAX];
 
// To count the prime triplets
// having the sum of the first two
// numbers equal to the third element
static int[] cntTriplet = new int[MAX];
 
// Function to count prime triplets
// having sum of the first two elements
// equal to the third element
static 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 Code
public static void main(String[] args)
{
    int N = 7;
    primeTriplet(N);
}
}
 
// This code is contributed by susmitakundugoaldagna.

# Python program for the above approach
 
# Function to count prime triplets
# having sum of the first two elements
# equal to the third element
def 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 Code
N = 7
primeTriplet(N)
 
# This code is contributed by rohitsingh07052

// C# Program to implement
// the above approach
using System;
class GFG
{
static int MAX = 1000001;
  
// Boolean array to
// mark prime numbers
static bool[] prime = new bool[MAX];
  
// To count the prime triplets
// having the sum of the first two
// numbers equal to the third element
static int[] cntTriplet = new int[MAX];
  
// Function to count prime triplets
// having sum of the first two elements
// equal to the third element
static 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 Code
public static void Main(String[] args)
{
    int N = 7;
    primeTriplet(N);
}
}
 
// This code is contributed by splevel62.

<script>
 
// Javascript program for the above approach
 
let MAX = 1000001
 
// Boolean array to
// mark prime numbers
let prime = new Array(MAX).fill(true);
 
// To count the prime triplets
// having the sum of the first two
// numbers equal to the third element
let cntTriplet = new Array(MAX).fill(0);
 
// Function to count prime triplets
// having sum of the first two elements
// equal to the third element
function 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 Code
 
let N = 7;
primeTriplet(N);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

2

Complejidad de tiempo: O(N * log(log(N)))
Espacio auxiliar: O(N)