Problemas com números primos

StackOverflow https://stackoverflow.com/questions/1877255

  •  18-09-2019
  •  | 
  •  

Pergunta

Eu estou tentando escrever um programa para encontrar o maior fator primordial de um número muito grande, e de ter tentado vários métodos com sucesso variável. Todos os que eu já encontrados até agora têm sido incrivelmente lento. Eu tinha um pensamento, e estou querendo saber se isso é uma abordagem válida: 

long number = input;

while(notPrime(number))
{
    number = number / getLowestDivisiblePrimeNumber();
}

return number;

Esta abordagem levaria uma entrada, e faria o seguinte:

200 -> 100 -> 50 -> 25 -> 5 (retorno)

90 -> 45 -> 15 -> 5 (regresso)

Ele divide currentNum repetidamente pelo menor número divisível (na maioria das vezes 2 ou 3) até si currentNum é primo (não há número primo divisível menos do que o squareroot de currentNum), e assume este é o maior fator primordial da entrada original.

Será que isso sempre funciona? Se não, alguém pode me dar um contra-exemplo?

-

EDIT:. Por muito grande, quero dizer cerca de 2 ^ 40, ou 10 ^ 11

Foi útil?

Solução

Esta será sempre trabalho por causa da exclusivo Prime Fatoração Teorema .

Outras dicas

O método funcionará, mas será lenta. "Como grandes são seus números?" Determina o método de usar:

Com certeza ele vai trabalhar (ver Mark Byers' resposta ), mas para "muito grande" inputs pode demorar muito tempo. Você deve observar que a sua chamada à esconde getLowestDivisiblePrimeNumber() outro ciclo, de modo que este é executado em O (n ^ 2), e que dependendo do que você quer dizer com "muito grande" ele pode ter que trabalhar em noreferrer bignums que será lenta.

Você pode acelerá-lo um pouco, notando que a sua necessidade algoritmo nunca verificar fatores menores do que o último encontrado.

Você está tentando encontrar o fatores primos de um número. O que você está propondo trabalho vontade, mas ainda será lenta para um grande número .... você deve ser grato por isso, já que a maioria de segurança moderno baseia-se este ser um problema difícil.

A partir de uma busca rápida eu fiz, a maneira mais rápida conhecido por fator de um número é usando o Elliptic Curve Method.

Você poderia tentar jogar seu número neste demonstração: http://www.alpertron.com .ar / ECM.HTM .

Se que convence você, você poderia tentar quer roubar o código (que não é divertido, eles fornecem um link para ele!) Ou lendo sobre a teoria de que em outros lugares. Há um artigo da Wikipedia sobre ele aqui: http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization mas eu sou burro demais para compreendê-lo. Felizmente, o problema é seu, não meu! :)

A coisa com o Project Euler é que geralmente há um método de força bruta óbvia a fazer o problema, que terá apenas sobre para sempre. À medida que as perguntas se tornam mais difíceis, você precisará implementar soluções inteligentes.

Uma forma de resolver este problema é usar um loop que sempre encontra o fator menor (inteiro positivo) de um número. Quando o menor fator de um número é esse número, então você encontrou o maior fator primordial!

Descrição detalhada Algoritmo:

Você pode fazer isso, mantendo três variáveis:

O número que você está tentando fator de (A) Uma loja divisor corrente (B) A maior loja de divisor (C)

Inicialmente, vamos (A) ser o número que você está interessado em - neste caso, é 600851475143. Então deixe (B) ser 2. Ter uma condicional que verifica se (A) é divisível por (B). Se for divisível, dividir (A) por (B), reset (B) a 2, e voltar para verificar se (A) é divisível por (B). Caso contrário, se (A) não é divisível por (B), o incremento (B) por 1 e, em seguida, verificar se a (A) é divisível por (B). Execute o loop até que (A) é 1. O (3) você retornar será o maior divisor primo de 600.851.475.143.

Há inúmeras maneiras que você poderia fazer isso mais eficaz - em vez de incremento para o próximo inteiro, você pode incrementar para o número inteiro seguinte necessariamente nobre, e em vez de manter a maior loja de divisor, você pode simplesmente devolver o número atual quando o seu única divisor é em si. No entanto, o algoritmo que eu descrevi acima será executado em segundos independentemente.

A implementação em python é a seguinte: - 

def lpf(x):
        lpf = 2;
        while (x > lpf):
                if (x%lpf==0):
                        x = x/lpf
                        lpf = 2
                else:
                        lpf+=1;
        print("Largest Prime Factor: %d" % (lpf));

def main():
        x = long(raw_input("Input long int:"))
        lpf(x);
        return 0;

if __name__ == '__main__':
    main()

Exemplo:. Vamos descobrir o maior fator primordial de 105 usando o método descrito acima

Seja (A) = 105. (B) = 2 (que sempre começam com 2), e não temos um valor para (C) ainda.

é (A) divisível por (B)? Não Incremento (B) por +1: (B) = 3. Is Is (A) divisível por (B)? Sim. (105/3 = 35). O maior divisor encontrado até agora é 3. Let (C) = 3. Update (A) = 35. Reset (B) = 2.

Agora, é (A) divisível por (B)? Não Incremento (B) por +1: 3. Is (A) divisível por (B) (B) =? Não Incremento (B) por +1: 4. Is (A) divisível por (B) (B) =? Não Incremento (B) por 1: 5. Is (A) divisível por (B) (B) =? Sim. (35/5 = 7). O maior divisor encontramos anteriormente é armazenado em (C). (C) é actualmente 3. 5 é maior do que 3, de modo que actualizar (C) = 5. actualização Nós (A) = 7. Nós reset (B) = 2.

Em seguida, repita o processo para (A), mas vamos apenas continuar incrementando (B) até (B) = (A), porque 7 é primo e não tem outros do que em si e 1. divisores (Nós já poderia parada quando (B)> ((a) / 2), como você não pode ter inteiro divisores maior do que metade de um número - o menor divisor possível (excepto 1) de qualquer número é 2)

Então, nesse ponto, voltamos (A) = 7.

Tente fazer alguns deles com a mão, e você vai pegar o jeito da ideia

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top