algorithm - primos - El factor primo más grande de un número

factores primos de 25

Question

¿Cuál es el mejor enfoque para calcular el factor principal más grande de un número?

Creo que el más eficiente sería el siguiente:

1. Encuentra el número primo más bajo que se divide limpiamente
2. Comprueba si el resultado de la división es primordial
3. Si no, encuentra el siguiente más bajo
4. Ir a 2.

Estoy basando esta suposición en que es más fácil calcular los factores primos pequeños. ¿Esto es 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 primos, por lo tanto, se necesita un algoritmo recursivo.

Editar nuevamente: 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 primordial del paso 2 resultaría en un primo más pequeño.

Answer 1

¡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;
    }

Answer 2

Aquí está la misma función @ Triptych proporcionada 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 máximo máximo se puede encontrar usando:

n= 373764623
max(primes(n))

y una lista de factores encontrados usando:

list(primes(n))

Answer 3

Aquí está mi enfoque para calcular rápidamente el factor principal más grande. Se basa en el hecho de que x modificado no contiene factores no primos. Para lograr eso, dividimos x tan pronto como se encuentra un factor. Entonces, lo único que queda es devolver el factor más grande. Sería ya primordial.

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

Answer 4

Aquí está mi intento en c #. La última impresión es el mayor factor primo del número. Lo revisé 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;
    }

  }
}

Answer 5

Código de 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);

Aquí hay un ejemplo del código :

Answer 6

Calcula el factor primo más grande de un número usando recursión 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
}

Answer 7

Calcule primero una lista que almacene números primos, por ej. 2 3 5 7 11 13 ...

Cada vez que factorice en primer lugar un número, utilice la implementación de Tríptico pero iterando esta lista de números primos en lugar de enteros naturales.

Answer 8

Con Java:

Para valores int :

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 valores long :

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

Answer 9

Creo que sería bueno almacenar en algún lugar todos los números primos posibles más pequeños que n y simplemente iterar a través de ellos para encontrar el divisor más grande. Puede obtener números primos de prime-numbers.org .

Por supuesto, supongo que tu número no es demasiado grande :)

Answer 10

El siguiente algoritmo de C ++ no es el mejor, pero funciona para números menores de 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;
 }

Answer 11

En realidad, hay varias maneras más eficientes de encontrar factores de grandes cantidades (para las pequeñas, 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 comprender e implementar. Desafortunadamente no es muy rápido en general.

El método más conocido para factorizar números de hasta 100 dígitos de largo es el tamiz cuadrático . Como beneficio adicional, parte del algoritmo se realiza fácilmente con procesamiento paralelo.

Otro algoritmo del que he oído hablar es el 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 haya decidido cómo dividir un número en dos factores, este es el algoritmo más rápido que se me ocurre para encontrar el mayor factor primo de un número:

Crea una cola de prioridad que inicialmente almacena el número en sí mismo. En cada iteración, eliminas el número más alto de la cola e intentas dividirlo en dos factores (sin dejar que el 1 sea uno de esos factores, por supuesto). Si este paso falla, ¡el número es primordial y usted tiene su respuesta! De lo contrario, agregue los dos factores en la cola y repita.

Answer 12

Enfoque iterativo de Python al eliminar 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

Answer 13

Este es 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:
Debajo está la versión O(sqrt(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

Answer 14

Estoy usando un algoritmo que continúa dividiendo el número por su factor principal 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()))) 

Entrada: 10 Salida: 5

Entrada: 600851475143 Salida: 6857

Answer 15

La respuesta aceptada ya señala que existen formas mucho más eficientes (como el tamiz cuadrático) para obtener los factores primos de un número dado, pero de todos modos la división de prueba es suficiente y también rápida para números pequeños si se utiliza la ayuda de Miller-Rabin. Por lo tanto, quiero mostrar cómo mejorar la división de prueba usando Miller-Rabin:

Nota: El código del algoritmo Miller-Rabin es una versión adaptada y ligeramente mejorada del Código Rosetta. El código fue probado usando Python 2.7.8 y Python 3.4.1

def int_sqrt(n):
    x = n
    y = (x + 1) >> 1
    while y < x:
        x = y
        y = (x + n // x) >> 1
    return x

def is_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True # n  is definitely composite

def is_prime(n):
    if n < 5:
        if n == 2 or n == 3:
            return True
        return False
    p = n % 6
    if p != 1 and p != 5:
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    if n < 2047: 
        return not is_composite(2, d, n, s)
    if n < 1373653: 
        return not any(is_composite(a, d, n, s) for a in (2, 3))
    if n < 9080191: 
        return not any(is_composite(a, d, n, s) for a in (31, 73))
    if n < 25326001: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5))
    if n < 118670087467: 
        if n == 3215031751: 
            return False
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7))
    if n < 2152302898747: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11))
    if n < 3474749660383: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13))
    if n < 341550071728321: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17))
    if n < 3825123056546413051: 
        return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23))
    return not any(is_composite(a, d, n, s) for a in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53))

def factorize(n):
    factors = []
    if n < 2: return factors
    if is_prime(n):
        factors.append(n)
        return factors
    while n % 2 == 0:
        n >>= 1
        factors.append(2)
    if n == 1: return factors
    max = int_sqrt(n) + 1
    i = 3
    while i < max:
        while n % i == 0:
            n = n // i
            factors.append(i)
        if n == 1: return factors
        if is_prime(n):
            factors.append(n)
            return factors
        i += 2
    return []

print(factorize(98768765456789876))

El resultado es:

[2, 2, 7, 23, 153367648224829]

Answer 16

La solución más simple es un par de funciones mutuamente recursivas .

La primera función genera todos los números primos:

1. Comience con una lista que consta de 2 y todos los números impares mayores que 2.
2. Elimina todos los números que no son primos. Es decir, números que no tienen factores primarios (que no sean ellos mismos). Vea abajo.

La segunda función devuelve los factores primos de un número dado n en orden creciente. La estrategia es intentar dividir n por cada primo que podría ser su divisor:

1. Tome una lista de todos los números primos en orden creciente (vea arriba).
2. Deje p ser un primo en esa lista, y ps sean los factores primos de n/p (vea el paso 1).
   • Si p cuadrado es mayor que nuestro número n , entonces n es primo. Hemos terminado.
   • Si p divide n , entonces p es un factor primordial de n . Los otros factores son ps .
   • De lo contrario, p no es un factor primordial de n .

El mayor factor primo de n es el último número dado por la segunda función.

Para aclarar, aquí está el código para 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

Answer 17

Me parece que el paso # 2 del algoritmo dado no será un enfoque tan eficiente. No tienes expectativas razonables de que sea excelente.

Además, la respuesta anterior que sugiere el tamiz de Eratóstenes es totalmente errónea. Acabo de escribir dos programas para el factor 123456789. Uno se basó en el tamiz, uno 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 Sieve.

El problema 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é, el Tamiz no. El tamiz usa muchas operaciones para eliminar todos los números compuestos.

Tenga en cuenta también que mis factores de división a medida que se identifican reducen el espacio que debe probarse.

Answer 18

Mi respuesta se basa en Triptych , pero mejora mucho en eso. 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;
}

Recientemente escribí un artículo de blog explicando cómo funciona este algoritmo.

Me atrevo a aventurar que un método en el que no hay necesidad de una prueba de primalidad (y no construcción de criba) sería más rápido que uno que sí los use. Si ese es el caso, este es probablemente el algoritmo más rápido aquí.

Answer 19

Probablemente esto no siempre sea más rápido, pero es más optimista al encontrar un gran divisor principal:

1. N es tu número
2. Si es primo, return(N)
3. Calcular números primos hasta Sqrt(N)
4. Ir a través de los números primos en orden descendente (el más grande primero)
   • Si N is divisible by Prime entonces Return(Prime)

Editar: en el paso 3 puedes usar el Tamiz de Eratóstenes o Tamiz de Atkins o lo que quieras, pero por sí solo el tamiz no te encontrará como el mayor factor primordial. (Es por eso que no elegiría la publicación de SQLMenace como respuesta oficial ...)

Answer 20

Similar a la respuesta de @Triptych pero también diferente. En este ejemplo, no se usa la lista o el 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

Answer 21

Soy consciente de que esta no es una solución rápida. Publicar como una solución lenta con suerte 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;
    } 

Answer 22

Todos los números se pueden expresar como el producto de números primos, por ejemplo:

102 = 2 x 3 x 17
712 = 2 x 2 x 2 x 89

Puede encontrarlos simplemente comenzando en 2 y simplemente continua dividiéndolo hasta que el resultado no sea un múltiplo de su número:

712 / 2 = 356 .. 356 / 2 = 178 .. 178 / 2 = 89 .. 89 / 89 = 1

utilizando este método no tiene que calcular ningún primo: todos serán números primos, basándose en el hecho de que ya ha factorizado el número tanto como sea posible con todos los números precedentes.

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

Answer 23

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

Answer 24

#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();
 }

Answer 25

#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

Answer 26

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 superflua, ya que n nunca se puede dividir por 6 si se han eliminado todos los factores 2 y 3. Solo puedes permitir primos para i, lo que se muestra en varias otras respuestas aquí.

En realidad, podría entrelazar el tamiz de Eratóstenes aquí:

• Primero crea la lista de enteros hasta sqrt (n).
• En el ciclo for, marque todos los múltiplos de i hasta el nuevo sqrt (n) como no primo, y use un ciclo while en su lugar.
• establecer i al próximo número primo en la lista.

También vea esta pregunta .