Dado un número n, la tarea es calcular su primorial. Primorial (denotado como P n #) es un producto de primeros n números primos. El primorial de un número es similar al factorial de un número. En primorial, no todos los números naturales se multiplican, solo los números primos se multiplican para calcular el primorial de un número. Se denota con P#.
Ejemplos:
Input: n = 3 Output: 30 Priomorial = 2 * 3 * 5 = 30 As a side note, factorial is 2 * 3 * 4 * 5 Input: n = 5 Output: 2310 Primorial = 2 * 3 * 5 * 7 * 11
Un enfoque ingenuo es verificar que todos los números del 1 al n uno por uno sean primos o no, en caso afirmativo, almacene la multiplicación en el resultado, de manera similar almacene el resultado de la multiplicación de números primos hasta n.
Un método eficiente es encontrar todos los números primos hasta n usando la criba de Sundaram y luego simplemente calcular el primorial multiplicándolos todos.
C++
// C++ program to find Primorial of given numbers
#include<bits/stdc++.h>
using namespace std;
const int MAX = 1000000;
// vector to store all prime less than and equal to 10^6
vector <int> primes;
// Function for sieve of sundaram. This function stores all
// prime numbers less than MAX in primes
void sieveSundaram()
{
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than MAX, we reduce MAX to half
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
bool marked[MAX/2 + 1] = {0};
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (int i = 1; i <= (sqrt(MAX)-1)/2 ; i++)
for (int j = (i*(i+1))<<1 ; j <= MAX/2 ; j += 2*i +1)
marked[j] = true;
// Since 2 is a prime number
primes.push_back(2);
// Print other primes. Remaining primes are of the
// form 2*i + 1 such that marked[i] is false.
for (int i=1; i<=MAX/2; i++)
if (marked[i] == false)
primes.push_back(2*i + 1);
}
// Function to calculate primorial of n
int calculatePrimorial(int n)
{
// Multiply first n primes
int result = 1;
for (int i=0; i<n; i++)
result = result * primes[i];
return result;
}
// Driver code
int main()
{
int n = 5;
sieveSundaram();
for (int i = 1 ; i<= n; i++)
cout << "Primorial(P#) of " << i << " is "
<< calculatePrimorial(i) <<endl;
return 0;
}
Java
// Java program to find Primorial of given numbers
import java.util.*;
class GFG{
public static int MAX = 1000000;
// vector to store all prime less than and equal to 10^6
static ArrayList<Integer> primes = new ArrayList<Integer>();
// Function for sieve of sundaram. This function stores all
// prime numbers less than MAX in primes
static void sieveSundaram()
{
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than MAX, we reduce MAX to half
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
boolean[] marked = new boolean[MAX];
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (int i = 1; i <= (Math.sqrt(MAX) - 1) / 2 ; i++)
{
for (int j = (i * (i + 1)) << 1 ; j <= MAX / 2 ; j += 2 * i + 1)
{
marked[j] = true;
}
}
// Since 2 is a prime number
primes.add(2);
// Print other primes. Remaining primes are of the
// form 2*i + 1 such that marked[i] is false.
for (int i = 1; i <= MAX / 2; i++)
{
if (marked[i] == false)
{
primes.add(2 * i + 1);
}
}
}
// Function to calculate primorial of n
static int calculatePrimorial(int n)
{
// Multiply first n primes
int result = 1;
for (int i = 0; i < n; i++)
{
result = result * primes.get(i);
}
return result;
}
// Driver code
public static void main(String[] args)
{
int n = 5;
sieveSundaram();
for (int i = 1 ; i <= n; i++)
{
System.out.println("Primorial(P#) of "+i+" is "+calculatePrimorial(i));
}
}
}
// This Code is contributed by mits
Python3
# Python3 program to find Primorial of given numbers
import math
MAX = 1000000;
# vector to store all prime less than and equal to 10^6
primes=[];
# Function for sieve of sundaram. This function stores all
# prime numbers less than MAX in primes
def sieveSundaram():
# In general Sieve of Sundaram, produces primes smaller
# than (2*x + 2) for a number given number x. Since
# we want primes smaller than MAX, we reduce MAX to half
# This array is used to separate numbers of the form
# i+j+2ij from others where 1 <= i <= j
marked=[False]*(int(MAX/2)+1);
# Main logic of Sundaram. Mark all numbers which
# do not generate prime number by doing 2*i+1
for i in range(1,int((math.sqrt(MAX)-1)/2)+1):
for j in range(((i*(i+1))<<1),(int(MAX/2)+1),(2*i+1)):
marked[j] = True;
# Since 2 is a prime number
primes.append(2);
# Print other primes. Remaining primes are of the
# form 2*i + 1 such that marked[i] is false.
for i in range(1,int(MAX/2)):
if (marked[i] == False):
primes.append(2*i + 1);
# Function to calculate primorial of n
def calculatePrimorial(n):
# Multiply first n primes
result = 1;
for i in range(n):
result = result * primes[i];
return result;
# Driver code
n = 5;
sieveSundaram();
for i in range(1,n+1):
print("Primorial(P#) of",i,"is",calculatePrimorial(i));
# This code is contributed by mits
C#
// C# program to find Primorial of given numbers
using System;
using System.Collections;
class GFG{
public static int MAX = 1000000;
// vector to store all prime less than and equal to 10^6
static ArrayList primes = new ArrayList();
// Function for sieve of sundaram. This function stores all
// prime numbers less than MAX in primes
static void sieveSundaram()
{
// In general Sieve of Sundaram, produces primes smaller
// than (2*x + 2) for a number given number x. Since
// we want primes smaller than MAX, we reduce MAX to half
// This array is used to separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
bool[] marked = new bool[MAX];
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2 ; i++)
{
for (int j = (i * (i + 1)) << 1 ; j <= MAX / 2 ; j += 2 * i + 1)
{
marked[j] = true;
}
}
// Since 2 is a prime number
primes.Add(2);
// Print other primes. Remaining primes are of the
// form 2*i + 1 such that marked[i] is false.
for (int i = 1; i <= MAX / 2; i++)
{
if (marked[i] == false)
{
primes.Add(2 * i + 1);
}
}
}
// Function to calculate primorial of n
static int calculatePrimorial(int n)
{
// Multiply first n primes
int result = 1;
for (int i = 0; i < n; i++)
{
result = result * (int)primes[i];
}
return result;
}
// Driver code
public static void Main()
{
int n = 5;
sieveSundaram();
for (int i = 1 ; i <= n; i++)
{
System.Console.WriteLine("Primorial(P#) of "+i+" is "+calculatePrimorial(i));
}
}
}
// This Code is contributed by mits
PHP
<?php
// PHP program to find Primorial
// of given numbers
$MAX = 100000;
// vector to store all prime less
// than and equal to 10^6
$primes = array();
// Function for sieve of sundaram.
// This function stores all prime
// numbers less than MAX in primes
function sieveSundaram()
{
global $MAX, $primes;
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than MAX, we reduce MAX
// to half. This array is used to
// separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
$marked = array_fill(0, $MAX / 2 + 1, 0);
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for ($i = 1; $i <= (sqrt($MAX) - 1) / 2 ; $i++)
for ($j = ($i * ($i + 1)) << 1 ;
$j <= $MAX / 2 ; $j += 2 * $i + 1)
$marked[$j] = true;
// Since 2 is a prime number
array_push($primes, 2);
// Print other primes. Remaining primes
// are of the form 2*i + 1 such that
// marked[i] is false.
for ($i = 1; $i <= $MAX / 2; $i++)
if ($marked[$i] == false)
array_push($primes, (2 * $i + 1));
}
// Function to calculate primorial of n
function calculatePrimorial($n)
{
global $primes;
// Multiply first n primes
$result = 1;
for ($i = 0; $i < $n; $i++)
$result = $result * $primes[$i];
return $result;
}
// Driver code
$n = 5;
sieveSundaram();
for ($i = 1 ; $i<= $n; $i++)
echo "Primorial(P#) of " . $i .
" is " . calculatePrimorial($i) . "\n";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find Primorial
// of given numbers
let MAX = 100000;
// vector to store all prime less
// than and equal to 10^6
let primes = new Array();
// Function for sieve of sundaram.
// This function stores all prime
// numbers less than MAX in primes
function sieveSundaram()
{
// In general Sieve of Sundaram,
// produces primes smaller than
// (2*x + 2) for a number given
// number x. Since we want primes
// smaller than MAX, we reduce MAX
// to half. This array is used to
// separate numbers of the form
// i+j+2ij from others where 1 <= i <= j
let marked = new Array(MAX / 2 + 1).fill(0);
// Main logic of Sundaram. Mark all numbers which
// do not generate prime number by doing 2*i+1
for (let i = 1; i <= (Math.sqrt(MAX) - 1) / 2 ; i++)
for (let j = (i * (i + 1)) << 1 ;
j <= MAX / 2 ; j += 2 * i + 1)
marked[j] = true;
// Since 2 is a prime number
primes.push(2);
// Print other primes. Remaining primes
// are of the form 2*i + 1 such that
// marked[i] is false.
for (let i = 1; i <= MAX / 2; i++)
if (marked[i] == false)
primes.push(2 * i + 1);
}
// Function to calculate primorial of n
function calculatePrimorial(n)
{
// Multiply first n primes
let result = 1;
for (let i = 0; i < n; i++)
result = result * primes[i];
return result;
}
// Driver code
let n = 5;
sieveSundaram();
for (let i = 1 ; i<= n; i++)
document.write("Primorial(P#) of " + i + " is " +
calculatePrimorial(i) + "<br>");
// This code is contributed by gfgking
</script>
Producción:
Primorial(P#) of 1 is 2 Primorial(P#) of 2 is 6 Primorial(P#) of 3 is 30 Primorial(P#) of 4 is 210 Primorial(P#) of 5 is 2310
Este artículo es una contribución de Sahil Chhabra (KILLER) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA