c# algorithm language-agnostic primes

c# - Proyecto Euler Pregunta 3 Ayuda



algorithm language-agnostic (16)

En realidad, para este caso no necesita verificar 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.

Estoy intentando trabajar con Project 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 factor primo más grande del número 600851475143?

Aquí está mi solución en C # y se ha estado ejecutando 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(); }

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

Aunque la pregunta requiere el factor primordial más grande , no necesariamente significa que debes encontrarlo primero ...

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.

Necesita reducir la cantidad de verificación que está haciendo ... piense en qué números necesita probar.

Para una mejor aproximación, lee sobre el Tamiz de Erathosthenes ... debería orientarte en la dirección correcta.

Para empezar, en lugar de comenzar su búsqueda en n / 2, comience en la raíz cuadrada de n. Obtendrás la mitad de los factores, la otra mitad será su complemento.

p.ej:

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.

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

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

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

  • Si n es par, desplazarse hacia la izquierda (dividir entre 2) hasta que ya no esté. Si es uno entonces, 2 es el factor principal más grande.
  • Si n no es par, no tienes que probar números pares.
  • Es cierto que puede detenerse en sqrt (n).
  • Solo tienes que probar los primos para conocer los factores. Sin embargo, podría ser más rápido probar si k divide n y luego probarlo en primalidad.
  • Puede optimizar el límite superior sobre la marcha cuando encuentra 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 superflua, ya que n nunca se puede dividir por 6 si se han eliminado todos los factores 2 y 3. Solo puedes permitir números primos para i.

Así como un ejemplo, veamos el resultado para 21:

21 no es par, entonces entramos en el bucle for con límite superior sqrt (21) (~ 4.6). Entonces 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 el resultado, que es n = 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 por debajo de 10 millones en <2s en una máquina decentemente rápida.

Para cada prima que encuentres, prueba dividirla en el número contra el que estás probando hasta que ya no puedas dividir los enteros. (es decir, verificar n % p == 0 y si es verdadero, luego dividir)

Una vez que n = 1 , has terminado. El último valor de n que se dividió con éxito es tu respuesta. En una nota al margen, también se encuentran todos los factores primos de n en el camino.

PD: Como se señaló 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.

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 ... Aviso, no hay necesidad de verificar primero ...

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

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

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)