Quale sarebbe un algoritmo appropriato per calcolare i numeri nell'intervallo di pochi miliardi?

Il mio approccio a questi problemi è di solito questo: costruisci l'algoritmo più semplice possibile per risolverlo, che di solito è un approccio ingenuo a forza bruta, e poi test / calcoli matematicamente se sia o meno troppo lento. Il più delle volte è abbastanza buono. Quando non lo è, hai un chiaro punto di partenza per lavorare e ottimizzare le cose finché l'algoritmo non è abbastanza efficiente.

Ecco un semplice algoritmo per risolvere il Problema 3 su Project Euler (in C, ma la sua traduzione in Python dovrebbe essere banale):

#include <stdio.h>
#include <math.h>

int isPrime(int n){
    int i;

    if (n==2)
        return 1;

    if (n%2==0)
        return 0;
    for (i=3;i<sqrt(n);i+=2)
        if (n%i==0)
            return 0;
    return 1;
}

int main(){
    long long int n = 600851475143;
    int i = 3;

    while (i<50000){
        if (isPrime(i))
            if (n%i==0)
                printf("%d\n",i);
        i+=2;
    }
    return 0;
}

Vale la pena scrivere un codice che faccia la fattorizzazione e l'individuazione primaria (fondamentalmente la stessa cosa) perché probabilmente riutilizzerai molte altre domande di Eulero. Sarai in grado di migliorare il codice per le domande successive e forse di esaminare i test di primalità non esaustivi se ritieni che non sia più abbastanza efficiente, quindi suggerisco che l'approccio più semplice per ora è:

• Scrivi un ciclo semplice che trovi tutti i numeri primi (ad esempio per ogni numero, prova la sua divisibilità per ogni primo trovato in precedenza, e se falliscono tutti, aggiungilo all'elenco dei primi).
• Cerca di dividere il numero che stai cercando di calcolare in base a ogni primo fino alla radice quadrata del numero.

In realtà questa è un'area di ricerca attiva in Matematica e Informatica. L'articolo di Wikipedia offre una buona panoramica:

link

Scegli qualsiasi algoritmo che ti piace / trova interessante e provaci.

Probabilmente dovresti fare un compromesso: la maggior parte degli algoritmi "buoni" richiede un bel po 'di background matematico per capire veramente (anche se potresti implementarli senza comprenderli completamente).

Se non sai da dove iniziare, ti consiglio il setaccio quadratico:

link

Non richiede folle conoscenza della matematica, ma funziona bene.

Ho risolto alcuni problemi di ProjectEuler qualche tempo fa in Ruby usando la divisione di prova con numeri primi .

Ho scoperto che la generazione dei numeri primi era molto più critica dell'algoritmo di fattorizzazione reale. Non appena ho sostituito il mio ingenuo approccio alla generazione di numeri primi con un setaccio i miei tempi di esecuzione sono scesi a un livello ragionevole.

Mantenerlo molto semplice ...

Trovare i fattori di X: vorrei iniziare (n) a 2 e lavorare fino all'intero (piano, non rotondo) della radice quadrata di X. Se dividendo X per n, Y e Y è un numero intero, sia n che Y sono fattori. I valori più bassi di n produrranno i valori più alti di Y.

Primality of Y: Again, loop (m) da 2 alla radice quadrata di Y e vedi se Y / m è un numero intero. Se è allora Y non è primo. Torna indietro per trovare un altro fattore.

Se m colpisce la radice di Y, hai il tuo numero primo. Basta guardare. Y è la risposta.

Se n colpisce la radice di X, non ci sono fattori primi.

Sto anche dando forma alla mia conoscenza di Python e ho anche iniziato a rispondere ai problemi di Project Euler sul mio repo github: link .

Per il problema 3, ho programmato una soluzione semplice basata sulle seguenti premesse:

1) dato un intero positivo n, comincio a dividerlo per 2, 3, ..., m, e se trovo che m è un fattore primo, lo aggiungo a una lista. Non sto aggiungendo alla lista multipli di fattori primi già scoperti. Ad esempio, 4 è un multiplo di 2, quindi 4 non viene aggiunto a questo elenco.

2) Quindi moltiplico ciascun numero primo nell'elenco per vedere se è uguale a n. Se uguale, abbiamo trovato tutti i fattori primi di n. In caso contrario, continua dividendo n per il numero m successivo, finché mutiplying tutti i fattori primi uguali n o m raggiunge n.

Per ulteriori dettagli, consulta link . Ho aggiunto commenti che ti aiuteranno a capire cosa ho programmato. È una soluzione semplice, e sono sicuro che non è la soluzione più veloce, ma funziona ed è abbastanza semplice da capire.

Distinti saluti

Poiché esiste già una soluzione completa, pubblicherò questo Haskell uno ...

--  Problem is to find the largest prime factor of 600851475143
module Factor (testval, bigfactor) where
  testval = 600851475143

  bf' :: Integer -> Integer -> Integer

  bf' f x | (f == x)         = f
          | ((mod x f) == 0) = bf' f (div x f)
          | True             = bf' (f+1) x

  bigfactor :: Integer -> Integer

  bigfactor x | (x <  1) = error "Parameter less than 1"
              | (x == 1) = 1
              | True     = bf' 2 x

Fondamentalmente, non è necessario testare la primalità. Se dividi i fattori che trovi (e assicurati di gestire i fattori ripetitivi), un fattore non primo non può mai verificarsi, perché un fattore non primo è un prodotto di fattori primi più piccoli.

Caricato e l'ho eseguito con GHCi: è istantaneo e ora ho risolto un totale di 4 (sì, quattro!) problemi di Eulero.