Primorial (P n #)

 Primorial 

PRIMORIAL DE UM NÚMERO

Dado um número n, a tarefa é calcular seu primorial. Primorial (denotado como P _n #) é um produto dos primeiros n números primos. Primorial de um número é semelhante ao fatorial de um número. No primorial, nem todos os números naturais são multiplicados, apenas os números primos são multiplicados para calcular o primorial de um número. É denotado com P #.

Exemplos: 

 

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 

Uma abordagem ingênua é verificar se todos os números de 1 a n um por um são primos ou não, se sim, então armazene a multiplicação no resultado, da mesma forma armazene o resultado da multiplicação dos primos até n.

Um método eficiente é encontrar todos os primos até n usando o Sieve of Sundaram e então calcular o primorial multiplicando todos eles.

 

// 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 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 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# 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 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
?>

<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>

Saída:  

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 artigo foi contribuído por Sahil Chhabra (KILLER) . Se você gosta de GeeksforGeeks e gostaria de contribuir, você também pode escrever um artigo usando write.geeksforgeeks.org ou enviar seu artigo para contrib@geeksforgeeks.org . Veja o seu artigo na página principal do GeeksforGeeks e ajude outros Geeks.

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.

• Primorial
• Origem: Wikipédia, a enciclopédia livre.

Na matemática, o primorial de um número natural n maior que 1 é denotado por ${\displaystyle �\mathrm{\#}}$ e é definido como o produto de todos os números primos menores ou iguais a n. O primorial de 1 é definido como sendo igual à unidade.

Exemplos

• ${\displaystyle 1\mathrm{\#}=1}$
• ${\displaystyle 2\mathrm{\#}=2}$
• ${\displaystyle 3\mathrm{\#}=2\cdot 3=6}$
• ${\displaystyle 4\mathrm{\#}=2\cdot 3=6}$
• ${\displaystyle 5\mathrm{\#}=2\cdot 3\cdot 5=30}$
• ${\displaystyle 6\mathrm{\#}=2\cdot 3\cdot 5=30}$
• ${\displaystyle 7\mathrm{\#}=2\cdot 3\cdot 5\cdot 7=210}$

Tabela de primoriais

Eis uma tabela de primoriais. Veja também (sequência A002110 na OEIS).

p	P(p)
2	2
3	6
5	30
7	210
11	2310
13	30030
17	510510
19	9699690
23	223092870
29	6469693230
31	200560490130
37	7420738134810
41	304250263527210
43	13082761331670030
47	614889782588491410
53	32589158477190044730
59	1922760350154212639070
61	117288381359406970983270
67	7858321551080267055879090
71	557940830126698960967415390
73	40729680599249024150621323470
79	3217644767340672907899084554130
83	267064515689275851355624017992790
89	23768741896345550770650537601358310

Estimativa de crescimento para o primorial

Para todo ${\displaystyle �\ge 1}$,  A demonstração se faz por indução matemática.

• Base:
  • 
  • 
• Indução
  • , n é par:

• • , n é ímpar, então escreve-se ${\displaystyle �=2�+1}$

Como cada número primo p,  é divisor de ${\displaystyle (\genfrac{}{}{0ex}{}{2�+1}{�+1})}$, temos que:

Agora, podemos estimar:

E o resultado segue.

Fatorial Página 01

Fatorial Página 02

Fatorial Página 03

(4!)² = (4 * 3* 2* 1) ² = 24² = 24 * 24 = 576