Encuentra el producto de los primeros N números primos

Dado un entero positivo N, calcula el producto de los primeros N números primos.

Ejemplos: 

Input : N = 3
Output : 30
Explanation : First 3 prime numbers are 2, 3, 5.

Input : N = 5
Output : 2310 

Acercarse:  

• Crea un tamiz que nos ayude a identificar si el número es primo o no en tiempo O(1). 
• Ejecute un bucle desde 1 hasta y a menos que encontremos n números primos. 
• Multiplica todos los números primos y desprecia los que no son primos. 
• Luego, muestre el producto de los primeros N números primos. 

Complejidad del tiempo – O( Nlog(logN) ) 

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

// C++ implementation of above solution
#include "cstring"
#include <iostream>
using namespace std;
#define MAX 10000
 
// 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[MAX + 1];
void SieveOfEratosthenes()
{
    memset(prime, true, sizeof(prime));
 
    prime[1] = false;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == true) {
 
            // Set all multiples of p to non-prime
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// find the product of 1st N prime numbers
int solve(int n)
{
    // count of prime numbers
    int count = 0, num = 1;
 
    // product of prime numbers
    long long int prod = 1;
 
    while (count < n) {
 
        // if the number is prime add it
        if (prime[num]) {
            prod *= num;
 
            // increase the count
            count++;
        }
 
        // get to next number
        num++;
    }
    return prod;
}
 
// Driver code
int main()
{
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5;
 
    // find the value of 1st n prime numbers
    cout << solve(n);
 
    return 0;
}

// Java implementation of above solution
 
class GFG
{
    static int MAX=10000;
 
    // 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.
    static boolean[] prime=new boolean[MAX + 1];
     
static void SieveOfEratosthenes()
{
 
    prime[1] = true;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == false) {
 
            // Set all multiples of p to non-prime
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = true;
        }
    }
}
 
// find the product of 1st N prime numbers
static int solve(int n)
{
    // count of prime numbers
    int count = 0, num = 1;
 
    // product of prime numbers
    int prod = 1;
 
    while (count < n) {
 
        // if the number is prime add it
        if (!prime[num]) {
            prod *= num;
 
            // increase the count
            count++;
        }
 
        // get to next number
        num++;
    }
    return prod;
}
 
// Driver code
public static void main(String[] args)
{
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5;
 
    // find the value of 1st n prime numbers
    System.out.println(solve(n));
 
}
}
// This code is contributed by mits

// C# implementation of above solution
 
class GFG
{
    static int MAX=10000;
 
    // 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.
    static bool[] prime=new bool[MAX + 1];
     
static void SieveOfEratosthenes()
{
 
    prime[1] = true;
 
    for (int p = 2; p * p <= MAX; p++) {
 
        // If prime[p] is not changed, then it is a prime
        if (prime[p] == false) {
 
            // Set all multiples of p to non-prime
            for (int i = p * 2; i <= MAX; i += p)
                prime[i] = true;
        }
    }
}
 
// find the product of 1st N prime numbers
static int solve(int n)
{
    // count of prime numbers
    int count = 0, num = 1;
 
    // product of prime numbers
    int prod = 1;
 
    while (count < n) {
 
        // if the number is prime add it
        if (!prime[num]) {
            prod *= num;
 
            // increase the count
            count++;
        }
 
        // get to next number
        num++;
    }
    return prod;
}
 
// Driver code
public static void Main()
{
    // create the sieve
    SieveOfEratosthenes();
 
    int n = 5;
 
    // find the value of 1st n prime numbers
    System.Console.WriteLine(solve(n));
 
}
}
// This code is contributed by mits

'''
python3 implementation of above solution'''
import math as mt
 
MAX=10000
 
'''
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(MAX+1)]
 
def SieveOfErastosthenes():
     
    prime[1]=False
     
    for p in range(2,mt.ceil(mt.sqrt(MAX))):
        #if prime[p] is not changes, then it is a prime
         
        if prime[p]:
            #set all multiples of p to non-prime
            for i in range(2*p,MAX+1,p):
                prime[i]=False
                 
#find the product of 1st N prime numbers
 
def solve(n):
    #count of prime numbers
    count,num=0,1
     
    #product of prime numbers
     
    prod=1
    while count<n:
        #if the number is prime add it
         
        if prime[num]:
            prod*=num
            #increase the count
             
            count+=1
        num+=1
    return prod
 
#Driver code
 
#create the sieve
SieveOfErastosthenes()
 
n=5
 
#find the value of 1st n prime numbers
print(solve(n))
 
#this code is contributed by Mohit Kumar 29
            

<?php
// PHP implementation of above solution
$MAX = 10000;
 
// 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 = array_fill(0, $MAX + 1, true);
 
function SieveOfEratosthenes()
{
    global $MAX;
    global $prime;
    $prime = array_fill(0, $MAX + 1, true);
    $prime[1] = false;
 
    for ($p = 2; $p * $p <= $MAX; $p++)
    {
 
        // If $prime[$p] is not changed,
        // then it is a $prime
        if ($prime[$p] == true)
        {
 
            // Set all multiples of $$p to non-$prime
            for ($i = $p * 2; $i <= $MAX; $i += $p)
                $prime[$i] = false;
        }
    }
}
 
// find the product of 1st N $prime numbers
function solve($n)
{
    global $prime;
     
    // $count of $prime numbers
    $count = 0;
    $num = 1;
 
    // product of $prime numbers
    $prod = 1;
 
    while ($count < $n)
    {
 
        // if the number is $prime add it
        if ($prime[$num]== true)
        {
            $prod *= $num;
 
            // increase the $count
            $count++;
        }
 
        // get to next number
        $num++;
    }
    return $prod;
}
 
// Driver code
 
// create the sieve
SieveOfEratosthenes();
 
$n = 5;
 
// find the value of 1st $n $prime numbers
echo solve($n);
 
// This code is contributed by ihritik
?>

<script>
// Javascript implementation of above solution
let MAX = 10000;
 
// 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.
let prime = new Array(MAX + 1).fill(true);
 
function SieveOfEratosthenes()
{
    prime[1] = false;
 
    for (let p = 2; p * p <= MAX; p++)
    {
 
        // If prime[p] is not changed,
        // then it is a prime
        if (prime[p] == true)
        {
 
            // Set all multiples of p to non-prime
            for (let i = p * 2; i <= MAX; i += p)
                prime[i] = false;
        }
    }
}
 
// find the product of 1st N prime numbers
function solve(n)
{   
    // count of prime numbers
    let count = 0;
    let num = 1;
 
    // product of prime numbers
    let prod = 1;
 
    while (count < n)
    {
 
        // if the number is prime add it
        if (prime[num]== true)
        {
            prod *= num;
 
            // increase the count
            count++;
        }
 
        // get to next number
        num++;
    }
    return prod;
}
 
// Driver code
 
// create the sieve
SieveOfEratosthenes();
 
let n = 5;
 
// find the value of 1st n prime numbers
document.write(solve(n));
 
// This code is contributed by Saurabh Jaiswal
</script>

2310

Espacio Auxiliar: O(MAX)

NOTA: Para valores más grandes de N, el producto puede dar errores de desbordamiento de enteros. 
También para consultas múltiples, se puede usar la técnica de array de prefijos que dará salida a cada consulta en O (1) después de hacer la array de prefijos primero, lo que tomará tiempo O (N).