Podemos calcular la descomposición en factores primos de un número «n» en O(sqrt(n)) como se explica aquí . Pero el método O(sqrt n) se agota cuando necesitamos responder múltiples consultas sobre la factorización prima.
En este artículo, estudiamos un método eficiente para calcular la factorización prima utilizando el espacio O(n) y la complejidad del tiempo O(log n) con precálculo permitido.
Prerrequisitos: Tamiz de Eratóstenes , Factor mínimo primo de números hasta n .
Concepto clave: nuestra idea es almacenar el factor primo más pequeño (SPF) para cada número. Luego, para calcular la descomposición en factores primos del número dado dividiendo recursivamente el número dado con su factor primo más pequeño hasta que se convierte en 1.
Para calcular el factor primo más pequeño para cada número usaremos la criba de eratóstenes . En el Sieve original, cada vez que marcamos un número como no primo, almacenamos el factor primo más pequeño correspondiente a ese número (consulte este artículo para una mejor comprensión).
Ahora, después de que terminemos de precalcular el factor primo más pequeño para cada número, dividiremos nuestro número n (cuya descomposición en factores primos se va a calcular) por su factor primo más pequeño correspondiente hasta que n se convierta en 1.
Pseudo Code for prime factorization assuming
SPFs are computed :
PrimeFactors[] // To store result
i = 0 // Index in PrimeFactors
while n != 1 :
// SPF : smallest prime factor
PrimeFactors[i] = SPF[n]
i++
n = n / SPF[n]
La implementación para el método anterior se da a continuación:
C++
// C++ program to find prime factorization of a
// number n in O(Log n) time with precomputation
// allowed.
#include "bits/stdc++.h"
using namespace std;
#define MAXN 100001
// stores smallest prime factor for every number
int spf[MAXN];
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
vector<int> getFactorization(int x)
{
vector<int> ret;
while (x != 1)
{
ret.push_back(spf[x]);
x = x / spf[x];
}
return ret;
}
// driver program for above function
int main(int argc, char const *argv[])
{
// precalculating Smallest Prime Factor
sieve();
int x = 12246;
cout << "prime factorization for " << x << " : ";
// calling getFactorization function
vector <int> p = getFactorization(x);
for (int i=0; i<p.size(); i++)
cout << p[i] << " ";
cout << endl;
return 0;
}
Java
// Java program to find prime factorization of a
// number n in O(Log n) time with precomputation
// allowed.
import java.util.Vector;
class Test
{
static final int MAXN = 100001;
// stores smallest prime factor for every number
static int spf[] = new int[MAXN];
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
static void sieve()
{
spf[1] = 1;
for (int i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i=4; i<MAXN; i+=2)
spf[i] = 2;
for (int i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible by i
for (int j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
static Vector<Integer> getFactorization(int x)
{
Vector<Integer> ret = new Vector<>();
while (x != 1)
{
ret.add(spf[x]);
x = x / spf[x];
}
return ret;
}
// Driver method
public static void main(String args[])
{
// precalculating Smallest Prime Factor
sieve();
int x = 12246;
System.out.print("prime factorization for " + x + " : ");
// calling getFactorization function
Vector <Integer> p = getFactorization(x);
for (int i=0; i<p.size(); i++)
System.out.print(p.get(i) + " ");
System.out.println();
}
}
Python3
# Python3 program to find prime factorization
# of a number n in O(Log n) time with
# precomputation allowed.
import math as mt
MAXN = 100001
# stores smallest prime factor for
# every number
spf = [0 for i in range(MAXN)]
# Calculating SPF (Smallest Prime Factor)
# for every number till MAXN.
# Time Complexity : O(nloglogn)
def sieve():
spf[1] = 1
for i in range(2, MAXN):
# marking smallest prime factor
# for every number to be itself.
spf[i] = i
# separately marking spf for
# every even number as 2
for i in range(4, MAXN, 2):
spf[i] = 2
for i in range(3, mt.ceil(mt.sqrt(MAXN))):
# checking if i is prime
if (spf[i] == i):
# marking SPF for all numbers
# divisible by i
for j in range(i * i, MAXN, i):
# marking spf[j] if it is
# not previously marked
if (spf[j] == j):
spf[j] = i
# A O(log n) function returning prime
# factorization by dividing by smallest
# prime factor at every step
def getFactorization(x):
ret = list()
while (x != 1):
ret.append(spf[x])
x = x // spf[x]
return ret
# Driver code
# precalculating Smallest Prime Factor
sieve()
x = 12246
print("prime factorization for", x, ": ",
end = "")
# calling getFactorization function
p = getFactorization(x)
for i in range(len(p)):
print(p[i], end = " ")
# This code is contributed
# by Mohit kumar 29
C#
// C# program to find prime factorization of a
// number n in O(Log n) time with precomputation
// allowed.
using System;
using System.Collections;
class GFG
{
static int MAXN = 100001;
// stores smallest prime factor for every number
static int[] spf = new int[MAXN];
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
static void sieve()
{
spf[1] = 1;
for (int i = 2; i < MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (int i = 4; i < MAXN; i += 2)
spf[i] = 2;
for (int i = 3; i * i < MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible by i
for (int j = i * i; j < MAXN; j += i)
// marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
static ArrayList getFactorization(int x)
{
ArrayList ret = new ArrayList();
while (x != 1)
{
ret.Add(spf[x]);
x = x / spf[x];
}
return ret;
}
// Driver code
public static void Main()
{
// precalculating Smallest Prime Factor
sieve();
int x = 12246;
Console.Write("prime factorization for " + x + " : ");
// calling getFactorization function
ArrayList p = getFactorization(x);
for (int i = 0; i < p.Count; i++)
Console.Write(p[i] + " ");
Console.WriteLine("");
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to find prime factorization
// of a number n in O(Log n) time with
// precomputation allowed.
$MAXN = 19999;
// stores smallest prime factor for
// every number
$spf = array_fill(0, $MAXN, 0);
// Calculating SPF (Smallest Prime Factor)
// for every number till MAXN.
// Time Complexity : O(nloglogn)
function sieve()
{
global $MAXN, $spf;
$spf[1] = 1;
for ($i = 2; $i < $MAXN; $i++)
// marking smallest prime factor
// for every number to be itself.
$spf[$i] = $i;
// separately marking spf for every
// even number as 2
for ($i = 4; $i < $MAXN; $i += 2)
$spf[$i] = 2;
for ($i = 3; $i * $i < $MAXN; $i++)
{
// checking if i is prime
if ($spf[$i] == $i)
{
// marking SPF for all numbers
// divisible by i
for ($j = $i * $i; $j < $MAXN; $j += $i)
// marking spf[j] if it is not
// previously marked
if ($spf[$j] == $j)
$spf[$j] = $i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
function getFactorization($x)
{
global $spf;
$ret = array();
while ($x != 1)
{
array_push($ret, $spf[$x]);
if($spf[$x])
$x = (int)($x / $spf[$x]);
}
return $ret;
}
// Driver Code
// precalculating Smallest
// Prime Factor
sieve();
$x = 12246;
echo "prime factorization for " .
$x . " : ";
// calling getFactorization function
$p = getFactorization($x);
for ($i = 0; $i < count($p); $i++)
echo $p[$i] . " ";
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to find prime factorization of a
// number n in O(Log n) time with precomputation
// allowed.
let MAXN = 100001;
// stores smallest prime factor for every number
let spf=new Array(MAXN);
// Calculating SPF (Smallest Prime Factor) for every
// number till MAXN.
// Time Complexity : O(nloglogn)
function sieve()
{
spf[1] = 1;
for (let i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (let i=4; i<MAXN; i+=2)
spf[i] = 2;
for (let i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible by i
for (let j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
// A O(log n) function returning primefactorization
// by dividing by smallest prime factor at every step
function getFactorization(x)
{
let ret =[];
while (x != 1)
{
ret.push(spf[x]);
x = Math.floor(x / spf[x]);
}
return ret;
}
// Driver method
// precalculating Smallest Prime Factor
sieve();
let x = 12246;
document.write("prime factorization for " + x + " : ");
// calling getFactorization function
let p = getFactorization(x);
for (let i=0; i<p.length; i++)
document.write(p[i] + " ");
document.write("<br>");
// This code is contributed by unknown2108
</script>
Producción:
prime factorization for 12246 : 2 3 13 157
Complejidad de tiempo : O(1)
Espacio Auxiliar: O(1)
Nota: el código anterior funciona bien para n hasta el orden de 10^7. Más allá de esto nos enfrentaremos a problemas de memoria.
Complejidad de tiempo: el precálculo para el factor primo más pequeño se realiza en O (n log log n) usando un tamiz. Mientras que en el paso de cálculo estamos dividiendo el número cada vez por el número primo más pequeño hasta que se convierte en 1. Entonces, consideremos el peor de los casos en el que cada vez que el SPF es 2. Por lo tanto tendrá log n pasos de división. Por lo tanto, podemos decir que nuestra complejidad de tiempo será O (log n) en el peor de los casos.
Este artículo es una contribución de Nitish Kumar . 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