Progetto Eulero Domanda 3

Question

Sto cercando di lavorare attraverso il Progetto di Eulero e sto colpendo una barriera sul problema del 03.Ho un algoritmo che funziona per piccoli numeri, ma il problema 3 si avvale di un molto, molto grande numero.

Problema 03: I fattori primi di 13195 sono 5, 7, 13 e 29.Qual è il più grande fattore primo del numero 600851475143?

Ecco la mia soluzione in C# ed è stato in esecuzione per penso che vicino a un'ora.Io non sto cercando una risposta perché mi vuole realmente risolvere questo me stesso.Soprattutto cerca di un po di aiuto.

    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

Per cominciare, invece di iniziare la ricerca da n / 2, avviarlo dalla radice quadrata di n. Otterrai la metà dei fattori, l'altra metà è il loro complemento.

es:

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;

Questo dovrebbe essere abbastanza veloce ... Nota, non c'è bisogno di controllare per prime ...

Answer 3

In realtà, per questo caso non è necessario controllare la primalità, basta rimuovere i fattori che trovi. Inizia con n == 2 e scansiona verso l'alto. Quando evil-big-number% n == 0, dividi evil-big-number per n e continua con un numero-evil-small-number. Fermati quando n & Gt; = sqrt (big-evil-number).

Non dovrebbe richiedere più di qualche secondo su qualsiasi macchina moderna.

Answer 4

Sebbene la domanda richieda il più grande fattore primo, non significa necessariamente che devi prima trovarne uno ...

Answer 5

Devi ridurre la quantità di controlli che stai facendo ... pensa a quali numeri devi testare.

Per un approccio migliore leggi su Sieve of Erathosthenes ... dovrebbe ottenere hai indicato nella giusta direzione.

Answer 6

Come per la ragione accettato nicf risposta:

È OK per il problema di Eulero, ma non la rende una soluzione efficiente nel caso generale.Perché vuoi provare anche i numeri per fattori?

• Se n è pari, spostamento a sinistra (dividere per 2) fino a quando non è più.Se è allora, 2 è il più grande primo il fattore.
• Se n non è ancora, non è necessario prova anche i numeri.
• È vero che ci si può fermare a sqrt(n).
• Devi solo numeri primi test per fattori.Potrebbe essere più veloce test se k divide n e poi prova per primalità però.
• È possibile ottimizzare il limite superiore il volo quando si trova un fattore.

Questo porterebbe a un po ' di codice come questo:

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)

Ci sono alcune modulo test guasta, come n non può mai essere diviso 6 se tutti i fattori 2 e 3 sono stati rimossi.Si potrebbe consentire solo i numeri primi per i.

Solo per fare un esempio consente di guardare il risultato per le 21:

21 non è ancora, così andiamo in loop con limite superiore sqrt(21) (~4.6).Possiamo quindi dividere 21 da 3, quindi risultato = 3 e n = 21/3 = 7.Abbiamo ora solo per testare fino a sqrt(7).che è più piccolo di 3, così abbiamo finito con il ciclo for.Torniamo al max di n e di risultato, che è n = 7.

Answer 7

Il modo in cui l'ho fatto è stato cercare i numeri primi (p), iniziando da 2 usando il setaccio di Eratostene. Questo algoritmo può trovare tutti i numeri primi sotto i 10 milioni in & Lt; 2s su una macchina abbastanza veloce.

Per ogni numero primo che trovi, prova a dividerlo per il numero che stai testando fino a quando non puoi più fare la divisione intera. (ad esempio, controlla n % p == 0 e, se vero, quindi dividi.)

Una volta n = 1, hai finito. L'ultimo valore di n che è stato diviso correttamente è la tua risposta. Su un sidenote, hai anche trovato tutti i fattori primi di 2 <= n <= sqrt(p) sulla strada.

PS: come notato in precedenza, devi solo cercare numeri primi tra <=>. Questo rende Sieve of Eratosthenes un algoritmo molto veloce e facile da implementare per i nostri scopi.

Answer 8

Una volta trovata la risposta, inserisci quanto segue nel tuo browser;)

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

Wofram Alpha è tuo amico

Answer 9

L'uso di un algoritmo ricorsivo in Java viene eseguito meno di un secondo ... pensa all'algoritmo un po 'perché include alcune " brute-force " che può essere eliminato. Guarda anche come lo spazio della tua soluzione può essere ridotto mediante calcoli intermedi.

Answer 10

Facile peasy in 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

Questa soluzione su C ++ ha richiesto 3,7 ms sul mio 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

Tutti i problemi di Project Euler dovrebbero richiedere meno di un minuto; anche un'implementazione ricorsiva non ottimizzata in Python richiede meno di un secondo [0,09 sec (cpu 4,3 GHz)].

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

potresti voler vedere questo: Esiste un semplice algoritmo che può determinare se X è primo e non confondere un semplice programmatore mortale?

e mi piace la soluzione di Lill mud:

  

richiedono " mathn.rb "
  mette 600851475143.prime_division.last.first

L'ho controllato qui

Answer 14

Forse è considerato un imbroglio, ma una possibilità in haskell è scrivere (per la cronaca ho scritto le righe da solo e non ho controllato i thread di eulerproject);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

Prova a utilizzare il Miller-Rabin Primality Test per verificare se un numero è primo . Ciò dovrebbe accelerare notevolmente le cose.

Answer 16

Un altro approccio è quello di ottenere prima tutti i numeri primi fino a n / 2 e quindi verificare se il modulo è 0. Un algoritmo che utilizzo per ottenere tutti i numeri primi fino a n può essere trovato qui .