Contar trillizos primos distintos hasta N tal que la suma de dos primos sea igual al tercer primo

Dado un número entero N , la tarea es contar el número de tripletes primos distintos (a, b, c) del rango [1, N] tales que a < b < c ≤ N y a + b = c .
Nota: Dos tuplas de primos son distintas si al menos uno de los primos presentes en ellas es diferente.

Ejemplos:

Entrada: N = 6
Salida: 1
Explicación: Entre los números en el rango [1, 6], el único triplete primo es (2, 3, 5) (Ya que 2 + 3 = 5).

Entrada: N = 10
Salida: 2
Explicación: Los distintos tripletes primos que satisfacen la condición son (2, 3, 5), (2, 5, 7).

Enfoque: El problema se puede resolver con base en la observación que se indica a continuación:

Observación: 

Para cada número primo p de 1 a N , es parte de un triplete si y solo si puede representarse como una suma de dos números primos . 
Dado que un número primo es un número impar, debe ser igual a la suma de un número par y un número impar. 
Por lo tanto, el único primo par es 2 . Por lo tanto, para que un número primo p constituya una tupla única (2, p-2, p), el número p – 2 debe ser un número primo .

Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos count = 0 , para almacenar el número de trillizos primos.
• Iterar de 1 a N y para cada número p , verificar si este número p y p – 2 son primos o no .
• Si son primos, entonces incremente el conteo en 1 .
• Imprime el valor de cuenta .

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is a prime or not
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 count the number
// of valid prime triplets
void countPrimeTuples(int N)
{
    // Stores the count
    // of prime triplets
    int count = 0;
 
    // Iterate from 2 to N and check for each
    // p, whether p & (p - 2) are prime or not
    for (int i = 2; i <= N; i++) {
 
        if (isPrime(i) && isPrime(i - 2))
            count++;
    }
 
    // Print the count obtained
    cout << count;
}
 
// Driver Code
int main()
{
    int N = 6;
    countPrimeTuples(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
class GFG
{
   
  // Function to check if a
  // number is a prime or not
  static boolean isPrime(int N)
  {
      if (N <= 1)
          return false;
      for (int i = 2; i <= Math.sqrt(N); i++)
      {
          if (N % i == 0)
              return false;
      }
      return true;
  }
 
  // Function to count the number
  // of valid prime triplets
  static void countPrimeTuples(int N)
  {
     
      // Stores the count
      // of prime triplets
      int count = 0;
 
      // Iterate from 2 to N and check for each
      // p, whether p & (p - 2) are prime or not
      for (int i = 2; i <= N; i++)
      {
          if (isPrime(i) && isPrime(i - 2))
              count++;
      }
 
      // Print the count obtained
      System.out.println(count);
  }
 
  // Driver Code
  public static void main (String[] args)
  { 
    int N = 6;
    countPrimeTuples(N);
  }
}
 
// This code is contributed by Dharanendra L V.

# Python3 program for the above approach
import math
 
# Function to check if a
# number is a prime or not
def isPrime(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 count the number
# of valid prime triplets
def countPrimeTuples(N) :
     
    # Stores the count
    # of prime triplets
    count = 0
 
    # Iterate from 2 to N and check for each
    # p, whether p & (p - 2) are prime or not
    for i in range(2, N + 1):
 
        if (isPrime(i) and isPrime(i - 2)) :
            count += 1
     
    # Print count obtained
    print(count)
 
# Driver Code
N = 6
countPrimeTuples(N)
 
# This code is contributed by susmitakundugoaldanga.

// C# program for the above approach
using System;
public class GFG
{
     
  // Function to check if a
  // number is a prime or not
  static bool isPrime(int N)
  {
      if (N <= 1)
          return false;
      for (int i = 2; i <= Math.Sqrt(N); i++)
      {
          if (N % i == 0)
              return false;
      }
      return true;
  }
 
  // Function to count the number
  // of valid prime triplets
  static void countPrimeTuples(int N)
  {
     
      // Stores the count
      // of prime triplets
      int count = 0;
 
      // Iterate from 2 to N and check for each
      // p, whether p & (p - 2) are prime or not
      for (int i = 2; i <= N; i++)
      {
          if (isPrime(i) && isPrime(i - 2))
              count++;
      }
 
      // Print the count obtained
      Console.WriteLine(count);
  }
 
  // Driver Code
  static public void Main ()
  {
    int N = 6;
    countPrimeTuples(N);
  }
}
 
// This code is contributed by Dharanendra L V.

<script>
 
// Javascript program for the above approach
 
// Function to check if a
// number is a prime or not
function isPrime(N)
{
    if (N <= 1)
        return false;
 
    for (let i = 2; i <= Math.sqrt(N); i++) {
        if (N % i == 0)
            return false;
    }
 
    return true;
}
 
// Function to count the number
// of valid prime triplets
function countPrimeTuples(N)
{
    // Stores the count
    // of prime triplets
    let count = 0;
 
    // Iterate from 2 to N and check for each
    // p, whether p & (p - 2) are prime or not
    for (let i = 2; i <= N; i++) {
 
        if (isPrime(i) && isPrime(i - 2))
            count++;
    }
 
    // Print the count obtained
    document.write(count);
}
 
// Driver Code
 
let N = 6;
countPrimeTuples(N);
 
// This code is contributed by _saurabh_jaiswal
 
</script>

1

Complejidad de Tiempo: O(N ^3/2 )
Espacio Auxiliar: O(1)