Contar números primos que se pueden expresar como suma de números primos consecutivos

Posted on by Rudeus Greyrat

Dado un número entero N , la tarea es encontrar el número de números primos hasta N que se pueden expresar como una suma de números primos consecutivos .

Ejemplos:

Entrada: N = 45
Salida: 3
Explicación:
A continuación se muestran los números primos hasta el 45 que se pueden expresar como suma de números primos consecutivos:

  • 5 = 2 + 3
  • 17 = 2 + 3 + 5 + 7
  • 41 = 2 + 3 + 5 + 7 + 11 + 13

Por lo tanto, la cuenta es 3. 

Entrada: N = 4
Salida: 0 

Enfoque: La idea es utilizar el algoritmo de prueba de primalidad . Usando esto, se pueden encontrar todos los primos que no excedan N. Después de eso, se puede encontrar cada número que se puede expresar como primos consecutivos. Siga los pasos a continuación para resolver el problema:

  1. Recorra cada número del 1 al N , verifique si es un número primo y lo almacenó en un vector .
  2. Ordena todos los números primos almacenados en el vector.
  3. Sean X primos presentes en el vector. Inicialice la suma como el primo más pequeño encontrado, es decir, el elemento en el índice 0 en el vector.
  4. Iterar sobre el rango [1, X – 1] y agregar cada elemento a la suma .
  5. Después de sumar, verifique si la suma es primo o no y si la suma es menor que N o no. Si resulta ser cierto, entonces incremente el contador. De lo contrario, si la suma se vuelve mayor que N , rompa el bucle.
  6. Después de todos los pasos anteriores, imprima el conteo de números primos almacenados en el contador .

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

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if a
// number is prime or not
int isprm(int n)
{
    // Base Case
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, sqrt(N)] to
    // detect primality of numbers
    for (int i = 5;
         i * i <= n; i = i + 6) {
 
        // If N is divisible by i
        // or i + 2
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }
 
    // Return 1 if N is prime
    return 1;
}
 
// Function to count the prime numbers
// which can be expressed as sum of
// consecutive prime numbers
int countprime(int n)
{
    // Initialize count as 0
    int count = 0;
 
    // Stores prime numbers
    vector<int> primevector;
 
    for (int i = 2; i <= n; i++) {
 
        // If i is prime
        if (isprm(i) == 1) {
            primevector.push_back(i);
        }
    }
 
    // Initialize the sum
    int sum = primevector[0];
 
    // Find all required primes upto N
    for (int i = 1;
         i < primevector.size(); i++) {
 
        // Add it to the sum
        sum += primevector[i];
        if (sum > n)
            break;
        if (isprm(sum) == 1) {
            count++;
        }
    }
 
    // Return the final count
    return count;
}
 
// Driver Code
int main()
{
    // Given number N
    int N = 45;
 
    // Function Call
    cout << countprime(N);
 
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
// Function to check if a
// number is prime or not
static int isprm(int n)
{
  // Base Case
  if (n <= 1)
    return  0;
  if (n <= 3)
    return 1;
  if (n % 2 == 0 ||
      n % 3 == 0)
    return 0;
 
  // Iterate till [5, Math.sqrt(N)]
  // to detect primality of numbers
  for (int i = 5; i * i <= n;
           i = i + 6)
  {
    // If N is divisible by i
    // or i + 2
    if (n % i == 0 ||
        n % (i + 2) == 0)
      return 0;
  }
 
  // Return 1 if N is prime
  return 1;
}
 
// Function to count the prime numbers
// which can be expressed as sum of
// consecutive prime numbers
static int countprime(int n)
{
  // Initialize count as 0
  int count = 0;
 
  // Stores prime numbers
  Vector<Integer> primevector =
                  new Vector<>();
 
  for (int i = 2; i <= n; i++)
  {
    // If i is prime
    if (isprm(i) == 1)
    {
      primevector.add(i);
    }
  }
 
  // Initialize the sum
  int sum = primevector.elementAt(0);
 
  // Find all required primes upto N
  for (int i = 1;
           i < primevector.size(); i++)
  {
    // Add it to the sum
    sum += primevector.elementAt(i);
    if (sum > n)
      break;
    if (isprm(sum) == 1)
    {
      count++;
    }
  }
 
  // Return the final count
  return count;
}
 
// Driver Code
public static void main(String[] args)
{
  // Given number N
  int N = 45;
 
  // Function Call
  System.out.print(countprime(N));
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 program for the above approach
 
# Function to check if a
# number is prime or not
def isprm(n):
     
    # Base Case
    if (n <= 1):
        return 0
    if (n <= 3):
        return 1
    if (n % 2 == 0 or n % 3 == 0):
        return 0
 
    # Iterate till [5, sqrt(N)] to
    # detect primality of numbers
    i = 5
    while (i * i <= n):
 
        # If N is divisible by i
        # or i + 2
        if (n % i == 0 or
            n % (i + 2) == 0):
            return 0
         
        i = i + 6
     
    # Return 1 if N is prime
    return 1
 
# Function to count the prime numbers
# which can be expressed as sum of
# consecutive prime numbers
def countprime(n):
     
    # Initialize count as 0
    count = 0
 
    # Stores prime numbers
    primevector = []
 
    for i in range(2, n + 1):
 
        # If i is prime
        if (isprm(i) == 1):
            primevector.append(i)
         
    # Initialize the sum
    sum = primevector[0]
 
    # Find all required primes upto N
    for i in range(1, len(primevector)):
 
        # Add it to the sum
        sum += primevector[i]
        if (sum > n):
            break
        if (isprm(sum) == 1):
            count += 1
 
    # Return the final count
    return count
 
# Driver Code
 
# Given number N
N = 45
 
# Function call
print(countprime(N))
 
# This code is contributed by code_hunt

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
// Function to check if a
// number is prime or not
static int isprm(int n)
{
  // Base Case
  if (n <= 1)
    return  0;
  if (n <= 3)
    return 1;
  if (n % 2 == 0 ||
      n % 3 == 0)
    return 0;
 
  // Iterate till [5, Math.Sqrt(N)]
  // to detect primality of numbers
  for (int i = 5; i * i <= n;
           i = i + 6)
  {
    // If N is divisible by i
    // or i + 2
    if (n % i == 0 ||
        n % (i + 2) == 0)
      return 0;
  }
 
  // Return 1 if N is prime
  return 1;
}
 
// Function to count the prime numbers
// which can be expressed as sum of
// consecutive prime numbers
static int countprime(int n)
{
  // Initialize count as 0
  int count = 0;
 
  // Stores prime numbers
  List<int> primevector = new List<int>();
 
  for (int i = 2; i <= n; i++)
  {
    // If i is prime
    if (isprm(i) == 1)
    {
      primevector.Add(i);
    }
  }
 
  // Initialize the sum
  int sum = primevector[0];
 
  // Find all required primes upto N
  for (int i = 1; i < primevector.Count; i++)
  {
    // Add it to the sum
    sum += primevector[i];
    if (sum > n)
      break;
    if (isprm(sum) == 1)
    {
      count++;
    }
  }
 
  // Return the readonly count
  return count;
}
 
// Driver Code
public static void Main(String[] args)
{
  // Given number N
  int N = 45;
 
  // Function Call
  Console.Write(countprime(N));
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program for the above approach
 
// Function to check if a
// number is prime or not
function isprm(n)
{
    // Base Case
    if (n <= 1)
        return 0;
    if (n <= 3)
        return 1;
    if (n % 2 == 0 || n % 3 == 0)
        return 0;
 
    // Iterate till [5, sqrt(N)] to
    // detect primality of numbers
    for (var i = 5;
         i * i <= n; i = i + 6) {
 
        // If N is divisible by i
        // or i + 2
        if (n % i == 0 || n % (i + 2) == 0)
            return 0;
    }
 
    // Return 1 if N is prime
    return 1;
}
 
// Function to count the prime numbers
// which can be expressed as sum of
// consecutive prime numbers
function countprime(n)
{
    // Initialize count as 0
    var count = 0;
 
    // Stores prime numbers
    var primevector = [];
 
    for (var i = 2; i <= n; i++) {
 
        // If i is prime
        if (isprm(i) == 1) {
            primevector.push(i);
        }
    }
 
    // Initialize the sum
    var sum = primevector[0];
 
    // Find all required primes upto N
    for (var i = 1;
         i < primevector.length; i++) {
 
        // Add it to the sum
        sum += primevector[i];
        if (sum > n)
            break;
        if (isprm(sum) == 1) {
            count++;
        }
    }
 
    // Return the final count
    return count;
}
 
// Driver Code
// Given number N
var N = 45;
// Function Call
document.write( countprime(N));
 
</script>
Producción: 

3

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

Enfoque eficiente: el enfoque anterior se puede optimizar precomputando los números primos hasta N usando la criba de Eratóstenes .

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

Publicación traducida automáticamente

Artículo escrito por rubaimandal3 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *