Ayuda del Proyecto Euler Pregunta 3

Question

Estoy intentando trabajar en el Proyecto Euler y me encuentro con una barrera en el problema 03.Tengo un algoritmo que funciona con números más pequeños, pero el problema 3 usa un número muy, muy grande.

Problema 03:Los factores primos de 13195 son 5, 7, 13 y 29.¿Cuál es el factor primo mayor del número 600851475143?

Aquí está mi solución en C# y creo que ha estado ejecutándose durante cerca de una hora.No estoy buscando una respuesta porque en realidad quiero resolver esto yo mismo.Principalmente solo busco ayuda.

    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 empezar, en lugar de comenzar su búsqueda en n / 2, comience en la raíz cuadrada de n. Obtendrá la mitad de los factores, la otra mitad es su complemento.

por ejemplo:

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;

Esto debería ser lo suficientemente rápido ... Tenga en cuenta que no hay necesidad de comprobar si hay prime ...

Answer 3

En realidad, para este caso no necesita verificar la originalidad, simplemente elimine los factores que encuentre. Comience con n == 2 y escanee hacia arriba. Cuando evil-big-number% n == 0, divida evil-big-number entre ny continúe con el número pequeño-evil-number. Deténgase cuando n & Gt; = sqrt (big-evil-number).

No debería tomar más de unos segundos en cualquier máquina moderna.

Answer 4

Aunque la pregunta pide el factor primo más grande , no necesariamente significa que tenga que encontrarlo primero ...

Answer 5

Debe reducir la cantidad de comprobación que está haciendo ... piense en los números que necesita probar.

Para un mejor enfoque, lea el Tamiz de Erathosthenes ... debe obtener apuntaste en la dirección correcta.

Answer 6

En cuanto a la razón para aceptar la respuesta de nicf:

Está bien para el problema en Euler, pero no lo convierte en una solución eficiente en el caso general. ¿Por qué intentarías números pares para los factores?

• Si n es par, desplazarse a la izquierda (dividir por 2) hasta que ya no lo sea. Si esto es uno entonces, 2 es el primo más grande factor.
• Si n no es par, no tiene que prueba números pares.
• Es cierto que puedes parar en sqrt (n).
• Solo tienes que probar primos para factores Puede ser más rápido probar si k divide ny luego lo prueba para primalidad sin embargo.
• Puede optimizar el límite superior en la mosca cuando encuentras un factor.

Esto llevaría a un 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)

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 puedes permitir primos para i.

Solo como ejemplo, veamos el resultado de 21:

21 no es par, así que vamos al bucle for con límite superior sqrt (21) (~ 4.6). Entonces podemos dividir 21 entre 3, por lo tanto, resultado = 3 yn = 21/3 = 7. Ahora solo tenemos que probar hasta sqrt (7). que es más pequeño que 3, por lo que hemos terminado con el bucle for. Devolvemos el máximo de ny el resultado, que es n = 7.

Answer 7

La forma en que lo hice fue buscar números primos (p), comenzando en 2 usando el Tamiz de Eratóstenes.Este algoritmo puede encontrar todos los números primos menores de 10 millones en <2 segundos en una máquina decentemente rápida.

Por cada número primo que encuentres, prueba divídelo entre el número con el que estás probando hasta que ya no puedas hacer más divisiones enteras.(es decir.controlar n % p == 0 y si es cierto, entonces divida.)

Una vez n = 1, ya terminaste.El último valor de n que dividido exitosamente es tu respuesta.Además, también has encontrado todos los factores primos de n en camino.

PD:Como se señaló antes, sólo necesita buscar números primos entre 2 <= n <= sqrt(p).Esto hace que el Tamiz de Eratóstenes sea un algoritmo muy rápido y fácil de implementar para nuestros propósitos.

Answer 8

Una vez que encuentre la respuesta, ingrese lo siguiente en su navegador;)

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

Wofram Alpha es tu amigo

Answer 9

El uso de un algoritmo recursivo en Java se ejecuta en menos de un segundo ... piense un poco en su algoritmo ya que incluye algunas & "; fuerza bruta &"; eso puede ser eliminado. Observe también cómo se puede reducir el espacio de su solución mediante cálculos intermedios.

Answer 10

Fácil guisante en 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 solución en C ++ tomó 3.7 ms en mi 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

Todos los problemas del Proyecto Euler deberían tomar menos de un minuto; incluso una implementación recursiva no optimizada en Python toma menos de un segundo [0.09 segundos (cpu 4.3GHz)].

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

es posible que desee ver esto: ¿Existe un algoritmo simple que pueda determinar si X es primo y no confundir a un simple programador mortal?

y me gusta la solución de lill mud:

  

requiere " mathn.rb "
  pone 600851475143.prime_division.last.first

Lo comprobé aquí

Answer 14

Tal vez se considere hacer trampa, pero una posibilidad en Haskell es escribir (para el registro escribí las líneas yo mismo y no he verificado los hilos del proyecto euler);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Intente utilizar la Prueba de primalidad de Miller-Rabin para comprobar si un número es primo . Eso debería acelerar las cosas considerablemente.

Answer 16

Otro enfoque es obtener todos los primos hasta n / 2 primero y luego verificar si el módulo es 0. Se puede encontrar un algoritmo que utilizo para obtener todos los números primos hasta n aquí .