Algoritmo para encontrar o maior fator primo de um número

Qual é a melhor abordagem para calcular o maior fator primo de um número?

Estou pensando que o mais eficiente seria o seguinte:

1. Encontre o número primo mais baixo que divide corretamente
2. Verifique se o resultado da divisão é primo
3. Caso contrário, encontre o próximo menor
4. Vá para 2.

Estou baseando essa suposição em que é mais fácil calcular os pequenos fatores primos. Isso é certo? Quais outras abordagens devo analisar?

Edit: Agora eu percebi que minha abordagem é inútil se houver mais de 2 fatores primos em jogo, uma vez que a etapa 2 falha quando o resultado é um produto de duas outras primas, portanto, é necessário um algoritmo recursivo.

Edite novamente: e agora percebi que isso ainda funciona, porque o último número primo encontrado deve ser o mais alto; portanto, qualquer teste adicional do resultado não primo da etapa 2 resultaria em um primo menor.

Na verdade, existem várias maneiras mais eficientes de encontrar fatores de grandes números (para os menores, a divisão de ensaios funciona razoavelmente bem).

Um método que é muito rápido se o número de entrada tiver dois fatores muito próximos de sua raiz quadrada é conhecido como fatoração de Fermat . Utiliza a identidade N = (a + b) (a - b) = a ^ 2 - b ^ 2 e é fácil de entender e implementar. Infelizmente, não é muito rápido em geral.

O método mais conhecido para calcular números de até 100 dígitos é a peneira quadrática . Como bônus, parte do algoritmo é facilmente executada com processamento paralelo.

Outro algoritmo de que ouvi falar é o algoritmo Rho de Pollard . Não é tão eficiente quanto a Peneira Quadrática em geral, mas parece ser mais fácil de implementar.

Depois de decidir como dividir um número em dois fatores, eis o algoritmo mais rápido em que consigo encontrar o maior fator primordial de um número:

Crie uma fila de prioridade que inicialmente armazene o número em si. A cada iteração, você remove o número mais alto da fila e tenta dividi-lo em dois fatores (não permitindo que 1 seja um desses fatores, é claro). Se esta etapa falhar, o número é primo e você tem a sua resposta! Caso contrário, você adiciona os dois fatores à fila e repete.

Aqui está o melhor algoritmo que eu conheço (em 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

O método acima é executado no O(n)pior dos casos (quando a entrada é um número primo).

EDIT:
Abaixo está a O(sqrt(n))versão, conforme sugerido no comentário. Aqui está o código, mais uma vez.

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

Minha resposta é baseada no Triptych , mas melhora muito. É baseado no fato de que além de 2 e 3, todos os números primos têm a forma 6n-1 ou 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;
}

Eu escrevi recentemente um artigo de blog explicando como esse algoritmo funciona.

Atrevo-me a que um método no qual não há necessidade de um teste de primalidade (e nenhuma construção de peneira) seja executado mais rapidamente do que aquele que os utiliza. Se for esse o caso, este é provavelmente o algoritmo mais rápido aqui.

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

Exemplo de uso:

let result = largestPrimeFactor(600851475143);

Aqui está um exemplo do código :

Semelhante à resposta @Triptych, mas também diferente. Neste exemplo, lista ou dicionário não é usado. O código está escrito em 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

Todos os números podem ser expressos como o produto de números primos, por exemplo:

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

Você pode encontrá-los simplesmente começando em 2 e continuando a dividir até o resultado não ser um múltiplo do seu número:

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

usando esse método, você não precisa calcular primos: eles serão primos, com base no fato de que você já fatorou o número o máximo possível com todos os 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
    }

A solução mais simples é um par de funções recursivas mutuamente .

A primeira função gera todos os números primos:

1. Comece com uma lista de todos os números naturais maiores que 1.
2. Remova todos os números que não são primos. Ou seja, números que não têm fatores primos (além de si mesmos). Ver abaixo.

A segunda função retorna os fatores primos de um determinado número nem ordem crescente.

1. Faça uma lista de todos os números primos (veja acima).
2. Remova todos os números que não são fatores de n.

O maior fator primo de né o último número fornecido pela segunda função.

Esse algoritmo requer uma lista lenta ou um idioma (ou estrutura de dados) com semântica chamada por necessidade .

Para esclarecimento, aqui está uma implementação (ineficiente) do acima mencionado em 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

Tornar isso mais rápido é apenas uma questão de ser mais inteligente sobre a detecção de quais números são primos e / ou fatores n, mas o algoritmo permanece o mesmo.

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)

Existem alguns testes de módulo que são supérfluos, pois n nunca pode ser dividido por 6 se todos os fatores 2 e 3 tiverem sido removidos. Você só pode permitir números primos para i, o que é mostrado em várias outras respostas aqui.

Você pode realmente entrelaçar a peneira de Eratóstenes aqui:

• Primeiro, crie a lista de números inteiros até sqrt (n).
• No loop for, marque todos os múltiplos de i até o novo sqrt (n) como não primo e use um loop while.
• defina i como o próximo número primo na lista.

Veja também esta pergunta .

Estou ciente de que essa não é uma solução rápida. Postagem como esperançosamente mais fácil de entender solução lenta.

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

Abordagem iterativa Python removendo todos os fatores primos do 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

Eu estou usando um algoritmo que continua dividindo o número pelo atual fator primo.

Minha solução em 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 Saída:5

Entrada: 600851475143 Saída:6857

Aqui está minha tentativa em c #. A última impressão é o maior fator principal do número. Eu verifiquei e 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 o maior fator primo de um número usando a recursão em C ++. O funcionamento do código é explicado abaixo:

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
}

Aqui está minha abordagem para calcular rapidamente o maior fator primo. É baseado no fato de que modificado xnão contém fatores não primos. Para conseguir isso, dividimos xassim que um fator é encontrado. Então, a única coisa que resta é retornar o maior fator. Já seria nobre.

O 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

O seguinte algoritmo C ++ não é o melhor, mas funciona para números abaixo de um bilhão e é muito 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;
 }

Encontrei esta solução na 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;
}

Fator principal usando a peneira:

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

Parece-me que o passo 2 do algoritmo dado não será uma abordagem tão eficiente. Você não tem uma expectativa razoável de que seja primordial.

Além disso, a resposta anterior que sugere a Peneira de Eratóstenes está totalmente errada. Acabei de escrever dois programas para o fator 123456789. Um foi baseado na peneira, um foi baseado no seguinte:

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 versão foi 90x mais rápida que a peneira.

O problema é que, nos processadores modernos, o tipo de operação importa muito menos que o número de operações, sem mencionar que o algoritmo acima pode ser executado em cache, o Sieve não. A peneira usa muitas operações eliminando todos os números compostos.

Observe, também, que a divisão dos fatores conforme identificados reduz o espaço que deve ser testado.

Calcule uma lista armazenando números primos primeiro, por exemplo, 2 3 5 7 11 13 ...

Toda vez que você fatorar um número primo, use a implementação do Triptych, mas iterando essa lista de números primos, em vez de números inteiros naturais.

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

Provavelmente nem sempre é mais rápido, mas mais otimista quanto ao fato de você encontrar um grande divisor principal:

1. N é o seu número
2. Se é primo, então return(N)
3. Calcular números primos até Sqrt(N)
4. Percorra os números primos em ordem decrescente (maior primeiro)
   • Se N is divisible by PrimeentãoReturn(Prime)

Editar: na etapa 3, você pode usar a peneira de Eratóstenes ou a peneira de Atkins ou o que quiser, mas por si só a peneira não encontrará o maior fator primordial. (É por isso que eu não escolheria a postagem do SQLMenace como resposta oficial ...)

Eu acho que seria bom armazenar em algum lugar todos os números possíveis menores que n e simplesmente percorrer eles para encontrar o maior divisor. Você pode obter primos em prime-numbers.org .

Claro que presumo que seu número não seja muito grande :)

Não é o mais rápido, mas 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;
    }

Aqui está a mesma função @ Triptych fornecida como gerador, que também foi ligeiramente simplificada.

def primes(n):
    d = 2
    while (n > 1):
        while (n%d==0):
            yield d
            n /= d
        d += 1

o max prime pode ser encontrado usando:

n= 373764623
max(primes(n))

e uma lista de fatores 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();
 }