Algoritmo para encontrar el factor primo más grande de un número
https://stackoverflow.com/questions/23287
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
¿Cuál es el mejor método para calcular el factor primo más grande de un número?
Estoy pensando que lo más eficiente sería el siguiente:
- Encuentra el número primo más bajo que divida limpiamente
- Comprueba si el resultado de la división es primo.
- Si no, busque el siguiente más bajo
- Ir a 2.
Baso esta suposición en que es más fácil calcular los factores primos pequeños.¿Es esto correcto?¿Qué otros enfoques debería considerar?
Editar:Ahora me he dado cuenta de que mi enfoque es inútil si hay más de 2 factores primos en juego, ya que el paso 2 falla cuando el resultado es un producto de otros dos factores primos, por lo que se necesita un algoritmo recursivo.
Editar de nuevo:Y ahora me he dado cuenta de que esto todavía funciona, porque el último número primo encontrado tiene que ser el más alto, por lo tanto, cualquier prueba adicional del resultado no primo del paso 2 daría como resultado un primo más pequeño.
Solución
En realidad, existen varias formas más eficientes de encontrar factores de números grandes (para los más pequeños, la división de prueba funciona razonablemente bien).
Un método que es muy rápido si el número de entrada tiene dos factores muy cercanos a su raíz cuadrada se conoce como Factorización de Fermat.Hace uso de la identidad N = (a + b)(a - b) = a^2 - b^2 y es fácil de entender e implementar.Lamentablemente no es muy rápido en general.
El método más conocido para factorizar números de hasta 100 dígitos es el tamiz cuadrático.Como beneficio adicional, parte del algoritmo se realiza fácilmente con procesamiento paralelo.
Otro algoritmo más del que he oído hablar es Algoritmo Rho de Pollard.No es tan eficiente como el Tamiz Cuadrático en general, pero parece ser más fácil de implementar.
Una vez que hayas decidido cómo dividir un número en dos factores, aquí tienes el algoritmo más rápido que se me ocurre para encontrar el factor primo más grande de un número:
Cree una cola de prioridad que inicialmente almacene el número en sí.En cada iteración, eliminas el número más alto de la cola e intentas dividirlo en dos factores (sin permitir que 1 sea uno de esos factores, por supuesto).Si este paso falla, ¡el número es primo y ya tienes tu respuesta!De lo contrario, agrega los dos factores a la cola y repite.
Otros consejos
Aquí está el mejor algoritmo que conozco (en Python)
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
El método anterior se ejecuta en O(n) en el peor de los casos (cuando la entrada es un número primo).
EDITAR:
abajo esta el O(sqrt(n)) versión, como se sugiere en el comentario.Aquí está el código, una vez más.
def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime factor list
Mi respuesta se basa en Tríptico's, pero mejora mucho.Se basa en el hecho de que más allá de 2 y 3, todos los números primos tienen la forma 6n-1 o 6n+1.
var largestPrimeFactor;
if(n mod 2 == 0)
{
largestPrimeFactor = 2;
n = n / 2 while(n mod 2 == 0);
}
if(n mod 3 == 0)
{
largestPrimeFactor = 3;
n = n / 3 while(n mod 3 == 0);
}
multOfSix = 6;
while(multOfSix - 1 <= n)
{
if(n mod (multOfSix - 1) == 0)
{
largestPrimeFactor = multOfSix - 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
if(n mod (multOfSix + 1) == 0)
{
largestPrimeFactor = multOfSix + 1;
n = n / largestPrimeFactor while(n mod largestPrimeFactor == 0);
}
multOfSix += 6;
}
Hace poco escribí un artículo de blog explicando cómo funciona este algoritmo.
Me atrevería a decir que un método en el que no hay necesidad de una prueba de primalidad (y sin construcción de tamiz) funcionaría más rápido que uno que sí los utilice.Si ese es el caso, este es probablemente el algoritmo más rápido aquí.
Código JavaScript:
'option strict';
function largestPrimeFactor(val, divisor = 2) {
let square = (val) => Math.pow(val, 2);
while ((val % divisor) != 0 && square(divisor) <= val) {
divisor++;
}
return square(divisor) <= val
? largestPrimeFactor(val / divisor, divisor)
: val;
}
Ejemplo de uso:
let result = largestPrimeFactor(600851475143);
Todos los números se pueden expresar como producto de números primos, por ejemplo:
102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89
Puedes encontrarlos simplemente comenzando en 2 y continuando dividiendo hasta que el resultado no sea un múltiplo de tu número:
712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1
Con este método no es necesario calcular ningún número primo:todos serán primos, basándose en el hecho de que ya has factorizado el número tanto como sea posible con todos los números anteriores.
number = 712;
currNum = number; // the value we'll actually be working with
for (currFactor in 2 .. number) {
while (currNum % currFactor == 0) {
// keep on dividing by this number until we can divide no more!
currNum = currNum / currFactor // reduce the currNum
}
if (currNum == 1) return currFactor; // once it hits 1, we're done.
}
//this method skips unnecessary trial divisions and makes
//trial division more feasible for finding large primes
public static void main(String[] args)
{
long n= 1000000000039L; //this is a large prime number
long i = 2L;
int test = 0;
while (n > 1)
{
while (n % i == 0)
{
n /= i;
}
i++;
if(i*i > n && n > 1)
{
System.out.println(n); //prints n if it's prime
test = 1;
break;
}
}
if (test == 0)
System.out.println(i-1); //prints n if it's the largest prime factor
}
Similar a la respuesta de @Triptych pero también diferente.En este ejemplo no se utiliza lista ni diccionario.El código está escrito en Ruby.
def largest_prime_factor(number)
i = 2
while number > 1
if number % i == 0
number /= i;
i -= 1
end
i += 1
end
return i
end
largest_prime_factor(600851475143)
# => 6857
La solución más sencilla es un par de mutuamente recursivo funciones.
La primera función genera todos los números primos:
- Comience con una lista de todos los números naturales mayores que 1.
- Elimina todos los números que no sean primos.Es decir, números que no tienen factores primos (aparte de ellos mismos).Vea abajo.
La segunda función devuelve los factores primos de un número dado. n en orden creciente.
- Tome una lista de todos los números primos (ver arriba).
- Elimina todos los números que no sean factores de
n.
El mayor factor primo de n es el último número dado por la segunda función.
Este algoritmo requiere un lista de espera o un lenguaje (o estructura de datos) con llamada por necesidad semántica.
Para aclarar, aquí hay una implementación (ineficiente) de lo anterior en Haskell:
import Control.Monad
-- All the primes
primes = 2 : filter (ap (<=) (head . primeFactors)) [3,5..]
-- Gives the prime factors of its argument
primeFactors = factor primes
where factor [] n = []
factor xs@(p:ps) n =
if p*p > n then [n]
else let (d,r) = divMod n p in
if r == 0 then p : factor xs d
else factor ps n
-- Gives the largest prime factor of its argument
largestFactor = last . primeFactors
Hacer esto más rápido es sólo una cuestión de ser más inteligente a la hora de detectar qué números son primos y/o factores de n, pero el algoritmo sigue siendo el mismo.
n = abs(number);
result = 1;
if (n mod 2 == 0) {
result = 2;
while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
if (n mod i == 0) {
result = i;
while (n mod i = 0) n /= i;
}
}
return max(n,result)
Hay algunas pruebas de módulo que son superfluas, ya que n nunca puede dividirse entre 6 si se han eliminado todos los factores 2 y 3.Solo podría permitir números primos para i, lo que se muestra en varias otras respuestas aquí.
De hecho, podrías entrelazar el tamiz de Eratóstenes aquí:
- Primero cree la lista de enteros hasta SQRT (N).
- En la marca FOR de bucle todos los múltiplos de I hasta el nuevo SQRT (N) como no primo, y use un bucle en su lugar.
- Establecer I en el siguiente número primo en la lista.
Ver también esta pregunta.
Soy consciente de que esta no es una solución rápida.Publicar como, con suerte, una solución lenta más fácil de entender.
public static long largestPrimeFactor(long n) {
// largest composite factor must be smaller than sqrt
long sqrt = (long)Math.ceil(Math.sqrt((double)n));
long largest = -1;
for(long i = 2; i <= sqrt; i++) {
if(n % i == 0) {
long test = largestPrimeFactor(n/i);
if(test > largest) {
largest = test;
}
}
}
if(largest != -1) {
return largest;
}
// number is prime
return n;
}
Enfoque iterativo de Python eliminando todos los factores primos del número
def primef(n):
if n <= 3:
return n
if n % 2 == 0:
return primef(n/2)
elif n % 3 ==0:
return primef(n/3)
else:
for i in range(5, int((n)**0.5) + 1, 6):
#print i
if n % i == 0:
return primef(n/i)
if n % (i + 2) == 0:
return primef(n/(i+2))
return n
Estoy usando un algoritmo que continúa dividiendo el número por su factor primo actual.
Mi solución en Python 3:
def PrimeFactor(n):
m = n
while n%2==0:
n = n//2
if n == 1: # check if only 2 is largest Prime Factor
return 2
i = 3
sqrt = int(m**(0.5)) # loop till square root of number
last = 0 # to store last prime Factor i.e. Largest Prime Factor
while i <= sqrt :
while n%i == 0:
n = n//i # reduce the number by dividing it by it's Prime Factor
last = i
i+=2
if n> last: # the remaining number(n) is also Factor of number
return n
else:
return last
print(PrimeFactor(int(input())))
Aporte : 10Producción : 5
Aporte : 600851475143 Producción : 6857
Aquí está mi intento en C#.La última impresión es el factor primo más grande del número.Lo comprobé y funciona.
namespace Problem_Prime
{
class Program
{
static void Main(string[] args)
{
/*
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
*/
long x = 600851475143;
long y = 2;
while (y < x)
{
if (x % y == 0)
{
// y is a factor of x, but is it prime
if (IsPrime(y))
{
Console.WriteLine(y);
}
x /= y;
}
y++;
}
Console.WriteLine(y);
Console.ReadLine();
}
static bool IsPrime(long number)
{
//check for evenness
if (number % 2 == 0)
{
if (number == 2)
{
return true;
}
return false;
}
//don't need to check past the square root
long max = (long)Math.Sqrt(number);
for (int i = 3; i <= max; i += 2)
{
if ((number % i) == 0)
{
return false;
}
}
return true;
}
}
}
#python implementation
import math
n = 600851475143
i = 2
factors=set([])
while i<math.sqrt(n):
while n%i==0:
n=n/i
factors.add(i)
i+=1
factors.add(n)
largest=max(factors)
print factors
print largest
Calcula el factor primo más grande de un número usando recursividad en C++.El funcionamiento del código se explica a continuación:
int getLargestPrime(int number) {
int factor = number; // assumes that the largest prime factor is the number itself
for (int i = 2; (i*i) <= number; i++) { // iterates to the square root of the number till it finds the first(smallest) factor
if (number % i == 0) { // checks if the current number(i) is a factor
factor = max(i, number / i); // stores the larger number among the factors
break; // breaks the loop on when a factor is found
}
}
if (factor == number) // base case of recursion
return number;
return getLargestPrime(factor); // recursively calls itself
}
Este es mi enfoque para calcular rápidamente el factor primo más grande.Se basa en el hecho de que modificado x no contiene factores no primos.Para lograrlo, dividimos x tan pronto como se encuentre un factor.Entonces, lo único que queda es devolver el factor más grande.Ya sería primo.
El código (Haskell):
f max' x i | i > x = max'
| x `rem` i == 0 = f i (x `div` i) i -- Divide x by its factor
| otherwise = f max' x (i + 1) -- Check for the next possible factor
g x = f 2 x 2
El siguiente algoritmo de C++ no es el mejor, pero funciona para números inferiores a mil millones y es bastante rápido.
#include <iostream>
using namespace std;
// ------ is_prime ------
// Determines if the integer accepted is prime or not
bool is_prime(int n){
int i,count=0;
if(n==1 || n==2)
return true;
if(n%2==0)
return false;
for(i=1;i<=n;i++){
if(n%i==0)
count++;
}
if(count==2)
return true;
else
return false;
}
// ------ nextPrime -------
// Finds and returns the next prime number
int nextPrime(int prime){
bool a = false;
while (a == false){
prime++;
if (is_prime(prime))
a = true;
}
return prime;
}
// ----- M A I N ------
int main(){
int value = 13195;
int prime = 2;
bool done = false;
while (done == false){
if (value%prime == 0){
value = value/prime;
if (is_prime(value)){
done = true;
}
} else {
prime = nextPrime(prime);
}
}
cout << "Largest prime factor: " << value << endl;
}
Encontré esta solución en la web por "James Wang"
public static int getLargestPrime( int number) {
if (number <= 1) return -1;
for (int i = number - 1; i > 1; i--) {
if (number % i == 0) {
number = i;
}
}
return number;
}
Factor primo usando tamiz:
#include <bits/stdc++.h>
using namespace std;
#define N 10001
typedef long long ll;
bool visit[N];
vector<int> prime;
void sieve()
{
memset( visit , 0 , sizeof(visit));
for( int i=2;i<N;i++ )
{
if( visit[i] == 0)
{
prime.push_back(i);
for( int j=i*2; j<N; j=j+i )
{
visit[j] = 1;
}
}
}
}
void sol(long long n, vector<int>&prime)
{
ll ans = n;
for(int i=0; i<prime.size() || prime[i]>n; i++)
{
while(n%prime[i]==0)
{
n=n/prime[i];
ans = prime[i];
}
}
ans = max(ans, n);
cout<<ans<<endl;
}
int main()
{
ll tc, n;
sieve();
cin>>n;
sol(n, prime);
return 0;
}
Me parece que el paso 2 del algoritmo dado no será un enfoque tan eficiente.No tiene ninguna expectativa razonable de que sea primo.
Además, la respuesta anterior que sugiere el Tamiz de Eratóstenes es completamente errónea.Acabo de escribir dos programas para factorizar 123456789.Uno se basó en el Tamiz, el otro se basó en lo siguiente:
1) Test = 2
2) Current = Number to test
3) If Current Mod Test = 0 then
3a) Current = Current Div Test
3b) Largest = Test
3c) Goto 3.
4) Inc(Test)
5) If Current < Test goto 4
6) Return Largest
Esta versión era 90 veces más rápida que la Sieve.
La cuestión es que, en los procesadores modernos, el tipo de operación importa mucho menos que el número de operaciones, sin mencionar que el algoritmo anterior puede ejecutarse en caché, mientras que Sieve no.El Tamiz utiliza muchas operaciones para tachar todos los números compuestos.
Tenga en cuenta también que al dividir los factores a medida que se identifican se reduce el espacio que se debe probar.
Calcule una lista que almacene primero los números primos, p.2 3 5 7 11 13 ...
Cada vez que factorices un número en factores primos, utiliza la implementación de Triptych pero iterando esta lista de números primos en lugar de números enteros naturales.
Con Java:
Para int valores:
public static int[] primeFactors(int value) {
int[] a = new int[31];
int i = 0, j;
int num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
int[] b = Arrays.copyOf(a, i);
return b;
}
Para long valores:
static long[] getFactors(long value) {
long[] a = new long[63];
int i = 0;
long num = value;
while (num % 2 == 0) {
a[i++] = 2;
num /= 2;
}
long j = 3;
while (j <= Math.sqrt(num) + 1) {
if (num % j == 0) {
a[i++] = j;
num /= j;
} else {
j += 2;
}
}
if (num > 1) {
a[i++] = num;
}
long[] b = Arrays.copyOf(a, i);
return b;
}
Probablemente esto no siempre sea más rápido, pero sí más optimista en cuanto a que encontrará un divisor primo grande:
Nes tu numero- Si es primo entonces
return(N) - Calcular números primos hasta
Sqrt(N) - Recorra los números primos en orden descendente (el más grande primero)
- Si
N is divisible by PrimeentoncesReturn(Prime)
- Si
Editar:En el paso 3 puedes usar el Tamiz de Eratóstenes o el Tamiz de Atkins o lo que quieras, pero por sí solo el tamiz no encontrará el factor primo más grande.(Es por eso que no elegiría la publicación de SQLMenace como respuesta oficial...)
Creo que sería bueno almacenar en algún lugar todos los números primos posibles más pequeños que n y simplemente recorrerlos en iteración para encontrar el divisor más grande.Puedes obtener números primos de números primos.org.
Por supuesto, supongo que tu número no es demasiado grande :)
¡No es el más rápido pero funciona!
static bool IsPrime(long num)
{
long checkUpTo = (long)Math.Ceiling(Math.Sqrt(num));
for (long i = 2; i <= checkUpTo; i++)
{
if (num % i == 0)
return false;
}
return true;
}
Aquí está la misma función que @Triptych proporciona como generador, que también se ha simplificado ligeramente.
def primes(n):
d = 2
while (n > 1):
while (n%d==0):
yield d
n /= d
d += 1
El primo máximo se puede encontrar usando:
n= 373764623
max(primes(n))
y una lista de factores encontrados usando:
list(primes(n))
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include <time.h>
factor(long int n)
{
long int i,j;
while(n>=4)
{
if(n%2==0) { n=n/2; i=2; }
else
{ i=3;
j=0;
while(j==0)
{
if(n%i==0)
{j=1;
n=n/i;
}
i=i+2;
}
i-=2;
}
}
return i;
}
void main()
{
clock_t start = clock();
long int n,sp;
clrscr();
printf("enter value of n");
scanf("%ld",&n);
sp=factor(n);
printf("largest prime factor is %ld",sp);
printf("Time elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
getch();
}
