Proyecto Euler Pregunta 3 Ayuda

Question

Estoy tratando de trabajar en el Proyecto Euler y estoy llegando a una barrera en el problema 03. Tengo un algoritmo que funciona para 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 mayor factor primo del número 600 851 475 143?

Aquí está mi solución en C# y ha estado funcionando durante cerca de una hora. No estoy buscando una respuesta porque realmente quiero resolver esto yo mismo. Principalmente buscando 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, inícielo en la raíz cuadrada de n. Obtendrás la mitad de los factores, la otra mitad será 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

es necesario reducir la cantidad de cheques que está haciendo ... pensar en lo que los números que necesita para poner a prueba.

Para una mejor aproximación lea en el Sieve of Erathosthenes ... debe hacerlo apuntar en la dirección correcta.

Answer 3

Pruebe usar el Miller-Rabin Primality Test para probar que un número sea el primero. Eso debería acelerar las cosas considerablemente.

Answer 4

pesar de que la pregunta se refiere a la más grande factor primordial, no necesariamente significa que usted tiene que encontrar primero que uno ...

Answer 5

En realidad, en este caso no es necesario para comprobar la primalidad , 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 smaller-evil-number. Detener cuando n> = sqrt (big-evil-number).

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

Answer 6

cuanto a la razón a la respuesta de nicf aceptado:

Está bien para el problema de Euler, pero no hace esta una solución eficiente en el caso general. ¿Por qué probaría los números pares para los factores?

• Si n es par, desplazar hacia la izquierda (dividir entre 2) hasta que ya no esté. Si es one then, 2 es el mayor factor primo .
• Si n no es par, no es necesario que pruebe los números pares.
• Es cierto que puede detenerse en sqrt (n).
• Solo tiene que probar los primos para los factores . Puede ser más rápido probar si k divide n y luego probarlo para primality.
• Puede optimizar el límite superior en la mosca cuando encuentre un factor.

Esto llevaría a algún 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 superfluo, como n no se puede dividir por 6 si todos los factores 2 y 3 se han eliminado. Solo puedes permitir números primos para i.

A modo de ejemplo veamos el resultado de 21:

21 no es uniforme, por lo que entra en el bucle for con sqrt límite superior (21) (~ 4,6). Podemos dividir 21 entre 3, por lo tanto result = 3 yn = 21/3 = 7. Ahora solo tenemos que probar hasta sqrt (7). que es más pequeño que 3, entonces hemos terminado con el ciclo for. Devolvemos el máximo de ny resultado, que es n = 7.

Answer 7

Otro enfoque es obtener todas las primas hasta n/2 primero y luego verificar si el módulo es 0. Algoritmo que uso para obtener todo los números primos hasta n se pueden encontrar here.

Answer 8

El uso de un algoritmo recursivo en Java se ejecuta en menos de un segundo ... piense un poco en su algoritmo, ya que incluye algo de "fuerza bruta" que puede eliminarse. También vea cómo su espacio de solución se puede reducir mediante cálculos intermedios.

Answer 9

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

Para cada prima que encuentre, pruebe dividirla en el número que está probando hasta que no pueda hacer la división de enteros nunca más. (es decir, marque n % p == 0 y si es verdadero, luego divida.)

Una vez que n = 1, ha terminado. El último valor de n que dividió con éxito es su respuesta. En resumen, también encontró todos los factores primos de n en el camino.

PD: Como se ha indicado anteriormente, solo 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 10

Todos los problemas de Project 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 11

es posible que desee ver esto: Is there a simple algorithm that can determine if X is prime, and not confuse a mere mortal programmer?

y me gustaría solución Lill de barro:

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

Lo he comprobado here

Answer 12

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 es necesario verificar la cebado ...

Answer 13

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

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

Wofram Alfa es su amigo

Answer 14

Peasy fácil 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 15

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 16

Tal vez se considere hacer trampa, pero una posibilidad en haskell es escribir (para el registro yo mismo escribí las líneas y no he comprobado los hilos de eulerproject);

import Data.Numbers.Primes 
last (primeFactors 600851475143)