Encuentra una secuencia de N números primos cuya suma sea un número compuesto

Dado un número entero N y la tarea es encontrar una secuencia de N números primos cuya suma sea un número compuesto.
Ejemplos: 
 

Entrada: N = 5 
Salida: 2 3 5 7 11 
2 + 3 + 5 + 7 + 11 = 28 que es compuesto.
Entrada: N = 6 
Salida: 3 5 7 11 13 17 
 

Enfoque: la suma de dos números primos siempre es par, que es compuesto, ya que son números impares excepto 2 . Hay dos casos ahora, 
 

  1. Cuando N es par , podemos imprimir cualquier N número primo excepto 2 y su suma siempre será par, es decir, los números impares cuando se suman un número par de veces darán una suma par.
  2. Cuando N es impar , podemos imprimir 2 y cualquier otro N – 1 primo para asegurarnos de que la suma sea par. Dado que N – 1 es par, la suma será par para todos los números primos excepto 2 , luego sumamos 2 como el número N para asegurarnos de que la suma siga siendo par.

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

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
 
// To store prime numbers
vector<int> v;
 
// Function to find and store
// all the primes <= n
void SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    bool prime[n + 1];
    memset(prime, true, sizeof(prime));
 
    for (int p = 2; p * p <= n; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[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)
                prime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            v.push_back(p);
}
 
// Function to print the required sequence
void GetSequence(int n)
{
 
    // If n is even then we do not include 2
    // and start the sequence from the 2nd
    // smallest prime else we include 2
    int i = (n % 2 == 0) ? 1 : 0;
 
    int cnt = 0;
    // Print the sequence
    while (cnt < n) {
        cout << v[i] << " ";
        i++;
        cnt++;
    }
}
 
// Driver code
int main()
{
    int n = 6;
    SieveOfEratosthenes(MAXN);
 
    GetSequence(n);
 
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG
{
     
static int MAXN = 100000;
 
// To store prime numbers
static Vector<Integer> v = new Vector<Integer>();
 
// Function to find and store
// all the primes <= n
static void SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    boolean[] prime = new boolean[n + 1];
    Arrays.fill(prime,true);
 
    for (int p = 2; p * p <= n; p++)
    {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[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)
                prime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            v.add(p);
}
 
// Function to print the required sequence
static void GetSequence(int n)
{
 
    // If n is even then we do not include 2
    // and start the sequence from the 2nd
    // smallest prime else we include 2
    int i = (n % 2 == 0) ? 1 : 0;
 
    int cnt = 0;
     
    // Print the sequence
    while (cnt < n)
    {
        System.out.print(v.get(i) + " ");
        i++;
        cnt++;
    }
}
 
// Driver code
public static void main(String[] args)
{
    int n = 6;
    SieveOfEratosthenes(MAXN);
 
    GetSequence(n);
}
}
 
// This code is contributed by Princi Singh

python

# Python3 implementation of the approach
 
MAXN=100000
 
# To store prime numbers
v=[]
 
# Function to find and store
# all the primes <= n
def SieveOfEratosthenes(n):
 
    # Create a boolean array "prime[0..n]" and initialize
    # all entries it as true. A value in prime[i] will
    # finally be false if i is Not a prime, else true.
    prime=[True for i in range(n + 1)]
 
    for p in range(2,n+1):
 
        # If prime[p] is not changed, then it is a prime
        if (prime[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(2 * p, n + 1, p):
                prime[i] = False
 
    # Store all the prime numbers
    for p in range(2, n + 1):
        if (prime[p]):
            v.append(p)
 
# Function to print the required sequence
def GetSequence(n):
 
    # If n is even then we do not include 2
    # and start the sequence from the 2nd
    # smallest prime else we include 2
    if n % 2 == 0:
        i = 1
    else:
        i = 0
 
    cnt = 0
    # Print the sequence
    while (cnt < n):
        print(v[i],end=" ")
        i += 1
        cnt += 1
 
 
# Driver code
n = 6
SieveOfEratosthenes(MAXN)
 
GetSequence(n)
 
# This code is contributed by mohit kumar 29

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
     
static int MAXN = 100000;
 
// To store prime numbers
static List<int> v = new List<int>();
 
// Function to find and store
// all the primes <= n
static void SieveOfEratosthenes(int n)
{
    // Create a boolean array "prime[0..n]" and initialize
    // all entries it as true. A value in prime[i] will
    // finally be false if i is Not a prime, else true.
    Boolean[] prime = new Boolean[n + 1];
    for(int i = 0; i < n + 1; i++)
        prime[i] = true;
 
    for (int p = 2; p * p <= n; p++)
    {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[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)
                prime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (int p = 2; p <= n; p++)
        if (prime[p])
            v.Add(p);
}
 
// Function to print the required sequence
static void GetSequence(int n)
{
 
    // If n is even then we do not include 2
    // and start the sequence from the 2nd
    // smallest prime else we include 2
    int i = (n % 2 == 0) ? 1 : 0;
 
    int cnt = 0;
     
    // Print the sequence
    while (cnt < n)
    {
        Console.Write(v[i] + " ");
        i++;
        cnt++;
    }
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 6;
    SieveOfEratosthenes(MAXN);
 
    GetSequence(n);
}
}
 
/* This code is contributed by PrinciRaj1992 */

Javascript

<script>
 
// Javascript implementation
// of the approach
 
var MAXN = 100000;
 
// To store prime numbers
var v = [];
 
// Function to find and store
// all the primes <= n
function SieveOfEratosthenes(n)
{
    // Create a boolean array
    // "prime[0..n]" and initialize
    // all entries it as true.
    // A value in prime[i] will
    // finally be false if i is Not a prime,
    // else true.
    var prime = Array(n + 1).fill(true);
    var p;
    for (p = 2; p * p <= n; p++) {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true) {
             var i;
            // 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)
                prime[i] = false;
        }
    }
 
    // Store all the prime numbers
    for (p = 2; p <= n; p++)
        if (prime[p])
            v.push(p);
}
 
// Function to print
// the required sequence
function GetSequence(n)
{
 
    // If n is even then we do not include 2
    // and start the sequence from the 2nd
    // smallest prime else we include 2
    var i = (n % 2 == 0) ? 1 : 0;
 
    var cnt = 0;
    // Print the sequence
    while (cnt < n) {
        document.write(v[i] + " ");
        i++;
        cnt++;
    }
}
 
// Driver code
    n = 6;
    SieveOfEratosthenes(MAXN);
    GetSequence(n);
 
</script>
Producción: 

3 5 7 11 13 17

 

Espacio Auxiliar: O(n)

Publicación traducida automáticamente

Artículo escrito por souradeep 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 *