Projeto Euler Pergunta 3 Ajuda

Question

Eu estou tentando trabalhar através do Projeto Euler e eu estou batendo uma barreira no problema 03. Eu tenho um algoritmo que funciona para números menores, mas o problema 3 usa uma muito, muito grande número.

Problema 03: Os fatores primos de 13195 são 5, 7, 13 e 29. Qual é o maior fator primordial do número 600851475143?

Aqui está a minha solução em C # e ele foi correndo para eu acho que perto de uma hora. Eu não estou procurando uma resposta, porque eu realmente quero resolver isso sozinho. Principalmente apenas à procura de alguma ajuda.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

Answer 1

Para começar, em vez de começar a sua busca em n / 2, inicie-o na raiz quadrada de n. Você terá metade dos factores, sendo a outra metade do seu complemento.

por exemplo:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

Answer 2

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

Isso deve ser suficiente rápida ... Aviso, não há necessidade de verificar se há privilegiada ...

Answer 3

Na verdade, para este caso não é necessário para verificar se há primality, basta remover os fatores que você encontrar. Comece com n == 2 e digitalizar para cima. Quando o mal-big-número% n == 0, dividir o mal-big-número por n e continuar com pequeno-mal-número. Parar quando n> = sqrt (big-mal-número).

não deve levar mais do que alguns segundos em qualquer máquina moderna.

Answer 4

Embora a questão pede a maior fator primordial, que não significa necessariamente que você tem que encontrar esse primeiro ...

Answer 5

Você precisa reduzir a quantidade de verificar que você está fazendo ... pensar sobre o que os números que você precisa para teste.

Para uma melhor abordagem ler sobre o Crivo de Erathosthenes ... ele deve ficar você apontou na direção certa.

Answer 6

Quanto à razão para a resposta de nicf aceita:

É OK para o problema em Euler, mas não faz isso uma solução eficiente no caso geral. Por que você tente mesmo números de fatores?

• Se n é par, desvio à esquerda (dividir por 2) até que não é mais. Se for um, em seguida, 2 é o maior primo fator.
• Se n não é mesmo, você não tem que teste números pares.
• É verdade que você pode parar em sqrt (n).
• Você só tem que primes de teste para fatores. Pode ser mais rápido para teste se divide k N e, em seguida, testá-lo para primality embora.
• Você pode otimizar o limite superior da a mosca quando você encontra um fator.

Isso levaria a algum código como este:

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 modulo que são superflous, como n nunca pode ser dividido por 6 se todos os fatores 2 e 3 foram removidos. Você só poderia permitir primos para i.

Apenas como exemplo, vamos olhar para o resultado de 21:

21 não é mesmo, então vamos para o loop com sqrt limite superior (21) (~ 4,6). Podemos então dividir por 21 3, por conseguinte, resultar = 3 e n = 21/3 = 7. Vamos agora só tem a testar até sqrt (7). que é menor, em seguida, 3, de modo que são feitas com o loop. Voltamos ao máximo de n e resultado, que é n = 7.

Answer 7

A maneira que eu fiz era para procurar números primos (p), a partir de 2, utilizando o Crivo de Eratóstenes. Este algoritmo pode encontrar todos os números primos menores de 10 milhões em <2s em uma máquina decentemente rápido.

Para cada nobre encontrar, dividir testá-lo para o número que você está testando contra até que você não pode fazer inteiro divisão mais. (Ie. Verificar n % p == 0 e se for verdade, então dividir.)

Uma vez n = 1, você está feito. O último valor de n que com sucesso dividido é sua resposta. Em uma nota, você também encontrou todos os fatores primos de n no caminho.

PS: Como foi observado antes, você só precisa procurar primos entre 2 <= n <= sqrt(p). Isso torna o Crivo de Eratóstenes um muito rápido e fácil de implementar algoritmo para nossos propósitos.

Answer 8

Uma vez que você encontrar a resposta, digite o seguinte no seu browser;)

http://www.wolframalpha.com/input/?i= FactorInteger (600851475143)

Wofram Alpha é seu amigo

Answer 9

Usando um algoritmo recursivo em Java é executado menos de um segundo ... acho que seu algoritmo por um pouco, uma vez que inclui alguns "forçando brute-" que pode ser eliminado. Também olhar como seu espaço de solução pode ser reduzido em cálculos intermédios.

Answer 10

Fácil peasy em C ++:

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

Answer 11

Esta solução em C ++ levou 3,7 ms na minha Intel Quad Core i5 iMac (3,1 GHz)

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

Answer 12

problemas do All Projeto Euler deve levar menos de um minuto; mesmo uma implementação recursiva unoptimized em Python leva menos de um segundo [0,09 segundos (4.3GHz CPU)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

Answer 13

Você pode querer ver isto: Existe um algoritmo simples que pode determinar se X é primo, e não confundir um simples programador mortal?

e eu como solução de lama lill:

exigem
"mathn.rb" puts 600851475143.prime_division.last.first

Eu verifiquei aqui

Answer 14

Talvez ele é considerado trapaça, mas uma possibilidade em Haskell é escrever (para o registro eu escrevi as linhas de mim e não tenho verificado tópicos eulerproject);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Tente utilizar o Miller-Rabin Primality Teste para teste para um número ser primo . Isso deve acelerar as coisas consideravelmente.

Answer 16

Outra abordagem é fazer com que todos os números primos até n / 2 e depois para verificar se o módulo é 0. Um algoritmo que eu uso para obter todos os números primos até n pode ser encontrada aqui .