Dado un número n, necesitamos encontrar el producto de todos los números primos entre 1 y n.
Ejemplos:
Input: 5 Output: 30 Explanation: product of prime numbers between 1 to 5 is 2 * 3 * 5 = 30 Input : 7 Output : 210
Usar la criba de Eratóstenes para encontrar todos los números primos del 1 al n y luego calcular el producto.
El siguiente es el algoritmo para encontrar todos los números primos menores o iguales a un número entero n por el método de Eratóstenes:
Cuando el algoritmo termina, todos los números de la lista que no están marcados son primos y usando un bucle calculamos el producto de los números primos.
C++
// CPP Program to find product
// of prime numbers between 1 to n
#include <bits/stdc++.h>
using namespace std;
// Returns product of primes in range from
// 1 to n.
long ProdOfPrimes(int n)
{
// Array to store prime numbers
bool prime[n + 1];
// 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.
memset(prime, true, n + 1);
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
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Return product of primes generated
// through Sieve.
long prod = 1;
for (int i = 2; i <= n; i++)
if (prime[i])
prod *= i;
return prod;
}
// Driver code
int main()
{
int n = 10;
cout << ProdOfPrimes(n);
return 0;
}
Java
// Java Program to find product
// of prime numbers between 1 to n
import java.util.Arrays;
class GFG {
// Returns product of primes in range from
// 1 to n.
static long ProdOfPrimes(int n)
{
// Array to store prime numbers
boolean prime[]=new boolean[n + 1];
// 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.
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
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Return product of primes generated
// through Sieve.
long prod = 1;
for (int i = 2; i <= n; i++)
if (prime[i])
prod *= i;
return prod;
}
// Driver code
public static void main (String[] args)
{
int n = 10;
System.out.print(ProdOfPrimes(n));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python3 Program to find product # of prime numbers between 1 to n # Returns product of primes # in range from 1 to n. def ProdOfPrimes(n): # Array to store prime numbers prime = [True for i in range(n + 1)] # 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. p = 2 while(p * p <= n): # If prime[p] is not changed, # then it is a prime if (prime[p] == True): # Update all multiples of p i = p * 2 while(i <= n): prime[i] = False i += p p += 1 # Return product of primes # generated through Sieve. prod = 1 for i in range(2, n+1): if (prime[i]): prod *= i return prod # Driver code n = 10 print(ProdOfPrimes(n)) # This code is contributed by Anant Agarwal.
C#
// C# Program to find product of
// prime numbers between 1 to n
using System;
public class GFG
{
// Returns product of primes
// in range from 1 to n.
static long ProdOfPrimes(int n)
{
// Array to store prime numbers
bool []prime=new bool[n + 1];
// 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.
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
for (int i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Return product of primes generated
// through Sieve.
long prod = 1;
for (int i = 2; i <= n; i++)
if (prime[i])
prod *= i;
return prod;
}
// Driver code
public static void Main ()
{
int n = 10;
Console.Write(ProdOfPrimes(n));
}
}
// This code is contributed by Sam007
PHP
<?php
// PHP Program to find product
// of prime numbers between 1 to n
// Returns product of primes
// in range from 1 to n.
function ProdOfPrimes($n)
{
// Array to store prime
// numbers 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();
for($i = 0; $i < $n + 1; $i++)
$prime[$i] = true;
for ($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
for ($i = $p * 2; $i <= $n;
$i += $p)
$prime[$i] = false;
}
}
// Return product of primes
// generated through Sieve.
$prod = 1;
for ($i = 2; $i <= $n; $i++)
if ($prime[$i])
$prod *= $i;
return $prod;
}
// Driver Code
$n = 10;
echo (ProdOfPrimes($n));
// This code is contributed by
// Manish Shaw(manishshaw1)
?>
Javascript
<script>
// Javascript Program to find product of
// prime numbers between 1 to n
// Returns product of primes
// in range from 1 to n.
function ProdOfPrimes(n)
{
// Array to store prime numbers
let prime = new Array(n + 1);
prime.fill(0);
// 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.
for(let i = 0; i < n + 1; i++)
prime[i] = true;
for (let 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
for (let i = p * 2; i <= n; i += p)
prime[i] = false;
}
}
// Return product of primes generated
// through Sieve.
let prod = 1;
for (let i = 2; i <= n; i++)
if (prime[i])
prod *= i;
return prod;
}
let n = 10;
document.write(ProdOfPrimes(n));
</script>
Producción:
210
Publicación traducida automáticamente
Artículo escrito por nickhilrawat y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA