Algoritmo para encontrar el factor primo más grande de un número

183

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

Estoy pensando que lo más eficiente sería lo siguiente:

  1. Encuentra el número primo más bajo que se divide limpiamente
  2. Compruebe si el resultado de la división es primo
  3. Si no, encuentre 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. ¿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 producto de otros dos números primos, por lo tanto, se necesita un algoritmo recursivo.

Edite 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 primo del paso 2 daría como resultado un primo menor.

mercutio
fuente
Mi enfoque fue: (1) dividir un número grande y posible entre 2; (2) verifique si el gran número se divide en partes iguales; (3) si es así, verifique si el número dividido por 2 es primo. Si es así, devuélvelo. (4) De lo contrario, reste 1 del número dividido por 2, volviendo al paso 3.
Kevin Meredith
1.encuentre cualquier número que se divida claramente (para i = 2 a int (sqr (num))) 2.divida por ese número (num = num / i) y repita hasta que no se encuentre nada en el intervalo de 1. 3. num es el factor más importante
user3819867
1
Podemos dividir con números primos pequeños, y el que finalmente queda, es el factor primo más grande (supongo)

Respuestas:

134

En realidad, hay 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 . Utiliza 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 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, aquí está 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 prioritaria que inicialmente almacena el número en sí. En cada iteración, elimina el número más alto de la cola e intenta dividirlo en dos factores (por supuesto, no permite que 1 sea uno de esos factores). Si este paso falla, ¡el número es primo y usted tiene su respuesta! De lo contrario, agrega los dos factores a la cola y repite.

Artelius
fuente
3
Pollard rho y el método de curva elíptica son mucho mejores para deshacerse de pequeños factores primos de su número que el tamiz cuadrático. QS tiene aproximadamente el mismo tiempo de ejecución sin importar el número. El enfoque más rápido depende de cuál sea su número; QS descifrará los números difíciles de factorizar más rápido, mientras que rho y ECM descifrarán los números fáciles de factorizar más rápido.
tmyklebu
Gracias por la sugerencia de variación cuadrática. Necesitaba implementar esto para uno de mis clientes, la versión inicial que obtuve fue algo similar a lo que @mercutio sugirió en su pregunta. La solución cuadrática es lo que está impulsando la herramienta de mi cliente ahora en math.tools/calculator/prime-factors .
Dors
Si hay una manera eficiente de resolver este problema, ¿no significa eso que el cifrado web no es seguro?
BKSpurgeon
141

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)el peor de los casos (cuando la entrada es un número primo).

EDITAR: a
continuación se muestra la 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
Tríptico
fuente
11
Lea y / o ejecute este código antes de rechazarlo. Funciona bien. Solo copia y pega. Como está escrito prime_factors (1000) devolverá [2,2,2,5,5,5], que debe interpretarse como 2 ^ 3 * 5 ^ 3, también conocido como factorización prima.
Tríptico
11
"corre en O(sqrt(n))el peor de los casos" - No, corre en O(n)el peor de los casos (por ejemplo, cuando nes primo)
Sheldon L. Cooper
16
Fácil de hacer O (sqrt (n)), simplemente detiene el ciclo cuando d * d> n, y si n> 1 en este punto, entonces su valor debe agregarse a la lista de factores primos.
Sumudu Fernando
55
¿Hay un nombre para esto?
Forethinker
11
dado que 2 es el único número primo par, por lo que en lugar de sumar 1 cada vez, puede iterar por separado para d = 2 y luego incrementarlo en 1 y luego desde d = 3 en adelante puede incrementar en 2. para que disminuya el número de iteraciones ... :)
tailor_raj
18

Mi respuesta se basa en el tríptico , 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;
}

Recientemente 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 los use. Si ese es el caso, este es probablemente el algoritmo más rápido aquí.

sundar - Restablecer a Monica
fuente
12
En realidad, puede llevar esta idea aún más lejos, por ejemplo, más allá de 2,3,5 todos los primos tienen la forma 30n + k (n> = 0) donde k solo toma aquellos valores entre 1 y 29 que no son divisibles por 2,3 o 5, es decir, 7,11,13,17,19,23,29. Incluso puede hacer que esto se adapte dinámicamente después de cada pocos primos que haya encontrado hasta ahora a 2 * 3 * 5 * 7 * ... * n + k donde k no debe ser divisible por ninguno de estos primos (tenga en cuenta que no todos los posibles k necesitan ser primordial, por ejemplo, para 210n + k tienes que incluir 121, de lo contrario te perderías 331 )
Tobias Kienzler
2
Supongo que debería serwhile (multOfSix - 1 <= n)
Nader Ghanbari
8

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

Aquí hay un ejemplo del código :

Vlad Bezden
fuente
7

Similar a la respuesta de @Triptych pero también diferente. En este ejemplo, no se usa la lista o diccionario. El código está escrito en Ruby.

def largest_prime_factor(number)
  i = 2
  while number > 1
    if number % i == 0
      number /= i;
    else
      i += 1
    end
  end
  return i
end

largest_prime_factor(600851475143)
# => 6857
Ugnius Malūkas
fuente
Finalmente algo legible e instantáneamente (en js) ejecutable al mismo tiempo. Estaba tratando de usar una lista de primos infinita y ya era demasiado lenta en 1 millón.
Ebuall
4

Todos los números se pueden expresar como el producto de 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 dividiendo 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

usando este método no tiene que calcular ningún primo: todos serán primos, basados ​​en el hecho de que ya ha 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.
}
nickf
fuente
Sí, pero esto es terriblemente ineficiente. Una vez que haya dividido todos los 2, realmente no debería intentar dividir entre 4, o por 6, o ...; Realmente es mucho más eficiente en el límite verificar solo números primos, o usar algún algoritmo adicional.
wnoise
66
+1 para compensar a wnoise, quien creo que está equivocado. Intentar dividir entre 4 solo sucederá una vez y fallará de inmediato. No creo que sea peor que eliminar 4 de alguna lista de candidatos, y ciertamente es más rápido que encontrar todos los números primos de antemano.
Tríptico
2
@Beowulf. Intente ejecutar este código antes de rechazarlo. Devuelve factores primos; simplemente no entiendes el algoritmo.
Tríptico
3
el código funciona bien, pero es lento si el número entrante es primo. Sin embargo, solo correría hasta el cuadrado e incrementaría en 2. Sin embargo, podría ser demasiado lento para números muy grandes.
blabla999
44
blabla999 tiene toda la razón. El ejemplo es 1234567898766700 = 2 * 2 * 5 * 5 * 12345678987667. Cuando llegamos currFactor = 3513642, sabemos que 12345678987667 es primo y debería devolverlo como respuesta. En cambio, este código continuará la enumeración hasta 12345678987667 en sí. Eso es 3,513,642x más lento de lo necesario.
Will Ness
4
    //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
    }
el_prole
fuente
1
¿Has probado tu código con 1,000,000,000,039? También debería funcionar en un abrir y cerrar de ojos. ¿Lo hace?
Will Ness
2
Podrías saberlo de antemano, sin intentarlo. 10 ^ 12 = (2 * 5) ^ 12 = 2 ^ 12 * 5 ^ 12. Entonces su whileciclo pasará por ivalores de 2,2,2,2,2,2,2,2,2,2,2,2, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5, 2,3,4,5. Todas las 60 iteraciones. Pero para (10 ^ 12 + 39) habrá (10 ^ 12 + 38) iteraciones, i=2,3,4,5,6,...,10^12+39. Incluso si 10 ^ 10 operaciones toman un segundo, 10 ^ 12 tomarán 100 segundos. Pero solo se necesitan 10 ^ 6 iteraciones, y si 10 ^ 10 operaciones toman un segundo, 10 ^ 6 tomarían 1/10 000 de segundo.
Will Ness
1
Porque no me di cuenta (10 ^ 12 + 39) era un número primo que hago ahora. Entiendo exactamente lo que estás diciendo.
the_prole
1
OK, entonces puedes cambiar tu código para que no haya una desaceleración tan grande para los primos: si n = a by a <= b, entonces a a <= b a = n, es decir a a <= n . Y si hemos alcanzado un + 1, entonces n es sin duda un primo. (haga ping si edita su respuesta para incorporar esto).
Will Ness
1
lo que sucede cuando long n = 2*1000000000039L? ¿Funciona tan rápido como debería? (también, ¿puede simplificar su código usando una return;declaración?). (si quieres que deje de empujarte, solo dilo;))
Will Ness
4

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

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

  1. Comience con una lista de todos los números naturales mayores que 1.
  2. Elimina todos los números que no son 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 nen orden creciente.

  1. Tome una lista de todos los números primos (ver arriba).
  2. Elimina todos los números que no son factores de n.

El factor primo más grande de nes el último número dado por la segunda función.

Este algoritmo requiere una lista perezosa o un lenguaje (o estructura de datos) con semántica llamada por necesidad .

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 solo una cuestión de ser más inteligente para detectar qué números son primos y / o factores n, pero el algoritmo sigue siendo el mismo.

Apocalipsis
fuente
2
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 se puede dividir por 6 si se han eliminado todos los factores 2 y 3. Solo podría permitir primos para i, que se muestra en varias otras respuestas aquí.

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

  • Primero cree la lista de enteros hasta sqrt (n).
  • En el bucle for, marque todos los múltiplos de i hasta el nuevo sqrt (n) como no primos, y use un bucle while en su lugar.
  • establezca i en el siguiente número primo de la lista.

También vea esta pregunta .

Ralph M. Rickenbach
fuente
2

Soy consciente de que esta no es una solución rápida. Publicar como es de esperar 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;
    } 
thejosh
fuente
1

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
Jyothir Aditya Singh
fuente
1

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

Entrada: 10 Salida:5

Entrada: 600851475143 Salida:6857

Kalpesh Dusane
fuente
0

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

  }
}
Seamus Barrett
fuente
0
#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
Rishabh Prasad
fuente
1
¿es 25 el factor primo más grande de 25?
Will Ness
0

Calcula el factor primo más grande de un número usando la 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
}
4aRk Kn1gh7
fuente
0

Aquí está mi enfoque para calcular rápidamente el factor primo más grande. Se basa en el hecho de que modificado xno contiene factores no primos. Para lograr eso, dividimosx tan pronto como se encuentra 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
penkovsky
fuente
¿Pero esto no intentará dividirse con todos los números pares también?
Janus Troelsen
0

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

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;
}
BabarBaig
fuente
0

Factor primo utilizando 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;
}
rashedcs
fuente
-1

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

Además, la respuesta anterior que sugiere el Tamiz de Eratóstenes es totalmente 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 fue 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é, el Sieve no. El tamiz utiliza muchas operaciones eliminando 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.

Loren Pechtel
fuente
eso es lo que dije, pero me rechazaron :( Creo que el problema es que si el número tiene un factor primo realmente grande (como él mismo), entonces este método debe recorrer todo el camino hasta ese número. En muchos casos sin embargo, este método es bastante eficiente.
nickf
Volver a leer el tuyo es lo mismo, pero la primera parte de la tuya es confusa.
Loren Pechtel
Trato de que en este número 143816789988504044536402352738195137863656439, que me haga saber qué tan eficiente es este ...
MichaelICE
-1

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

Cada vez que factoriza un número primo, use la implementación por Triptych pero iterando esta lista de números primos en lugar de enteros naturales.

guoger
fuente
-1

Con Java:

Para intvalores:

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

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;
}
Paul Vargas
fuente
-2

Probablemente esto no siempre sea más rápido, pero es más optimista acerca de que encuentre un gran divisor principal:

  1. N es tu numero
  2. Si es primo entonces return(N)
  3. Calcular 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 PrimeentoncesReturn(Prime)

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

palotasb
fuente
1
¿No necesita hacer el factoring de prueba para determinar si es un número primo (paso 2)? Además, considere encontrar el factor primo más grande de 15. Los primos hasta sqrt (15) son 2 y 3; pero el factor primo más grande es 5, ¿no es así? De manera similar con 20.
Jonathan Leffler
-3

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

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

Klesk
fuente
-3

¡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;
    }
Mella
fuente
Esta no es una respuesta a la pregunta. ;-) La pregunta era sobre encontrar el factor primo más grande, no verificar la primalidad.
Hans-Peter Störr el
Es mucho más eficiente inicializar su ciclo como (largo i = 3; i <checkUpTo; i + = 2)
cjk
-3

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 primo se puede encontrar usando:

n= 373764623
max(primes(n))

y una lista de factores encontrados usando:

list(primes(n))
pedram
fuente
-6
#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();
 }
Chitransh
fuente