[C++] Calcolo del milionesimo numero primo

di il
10 risposte

[C++] Calcolo del milionesimo numero primo

Ciao a tutti . Sto cercando di ottimizzare il più possibile il seguente programma che calcola il milionesimo numero primo . Sono arrivato a 25 secondi, cosa fareste voi per ridurre il tempo di esecuzione? Grazie

#include <iostream>
#include <math.h>
using namespace std;
bool funz(int numero){
    double radice=sqrt(numero);
    bool verifica=true;
    for(int i=2;i<=radice;i++){
        if(numero%i==0){
            verifica=false;
            return verifica;
            break;
            }
    }
    return verifica;
}int main()
{
    int numero=2;
    int contatore=1;
    while(contatore<=1000000){
        if(funz(numero))
            contatore++;
        numero++;
    }
    cout<<""<<(numero-1)<<endl;
}

10 Risposte

  • Re: [C++] Calcolo del milionesimo numero primo

    Butta via dell'assurdità mangiacicli e usa un crivello di Eratostene (o magari di Atkin), che è almeno cinquanta o cento volte più veloce pur essendo un algoritmo esaustivo.

    Inoltre cerca di dare un titolo più significativo al thread (per questa volta ho provveduto io) e usa i tag code per presentare il codice sorgente (idem).
  • Re: [C++] Calcolo del milionesimo numero primo

    Per trovare se un numero è primo ci sono modi infinitamente migliori dello stesso tipo tuo. Prendi questo per esempio
    
    bool primo(int num)
    {
      if(num<2||num%2==0)
        return false;
      int i;
      for(i=3;i<=sqrt(num);i+=2)
        if(num%i==0)
          return false;
      return true;
    }
    
    Oppure uno ancora più veloce è quello di usare un array di fattori primi inizialmente col numero 2, e ogni numero lo dividi solo per quelli presenti nell'array, e se ne trovi uno primo lo aggiungi nell'array
  • Re: [C++] Calcolo del milionesimo numero primo

    M.A.W. 1968 ha scritto:


    Butta via dell'assurdità mangiacicli e usa un crivello di Eratostene (o magari di Atkin), che è almeno cinquanta o cento volte più veloce pur essendo un algoritmo esaustivo.
    Scusa ma a me non pare che sia molto più veloce. Alla fine si tratta sempre di dividere tanti numeri per tanti altri numeri. Secondo me il metodo più veloce è quello dei fattori primi. Avevo scritto un programma (che ora ho perso e non sono più in grado di riprodurlo purtroppo) che arrivava al milione in meno di un decimo di secondo
  • Re: [C++] Calcolo del milionesimo numero primo

    Non si usano divisioni, né moltiplicazioni nel crivello di Erastotene; bensì solo addizioni e shift. Prima di rispondere avresti fatto meglio a cercarti un'ottima implementazione dello stesso. In ogni caso questo è il link che ti serve http://forum.ubuntu-it.org/viewtopic.php?f=33&t=602811&hilit=erastotene.
  • Re: [C++] Calcolo del milionesimo numero primo

    ANDPRI ha scritto:


    Scusa ma a me non pare che sia molto più veloce.
    Una frase informaticamente priva di significato, scritta da un ragazzino con meno di un anno di "esperienza" in ambito di programmazione. Per giunta, rivolta ad un matematico computazionale con 35 anni di esperienza pratica...

    Non possiedi neppure gli strumenti per valutare la complessità computazionale di un algoritmo. In informatica "a ma non pare" è del tutto irrilevante, specialmente in una condizione di asimmetria informativa a dir poco disastrosa come quella che ci separa. Infatti nel resto del post ti riveli del tutto disinformato: i metodi di crivello non sono basati su divisione o moltiplicazione (operazioni penalizzatissime in ambito x86 e IA64), a meno che non siano scritti da qualche sprovveduto improvvisatore. I crivelli sono intrinsecamente additivi, con dei banali trucchi algebrici e opportune strutture dati possono essere resi ulteriormente efficienti. Sicuramente miriadi di volte più efficienti degli algoritmi di fattorizzazione naif che possono passare per le mani di dilettanti ed esordienti, come d'altronde è mostrato in tutti i testi di teoria computazionale del numero, dai più banali ai più sofisticati. Se vuoi imparare qualcosa sui crivelli (ed è solo l'inizio dell'inizio), studia con estrema attenzione il link fornito da loopunrolling, tanto per cominciare. E in quel contesto, per restare sul semplice, non ci siamo neppure inoltrati nelle ulteriori ottimizzazioni che separano Eratostene da Atkin, a cominciare dall'incremento della variabile di induzione che può procedere con la successione dei quadrati anziché per raddoppio, usando un array di booleani convenzionale.

    Come ti è già stato ripetuto almeno mezza dozzina di volte al giorno ultimamente, senza conoscere approfonditamente la teoria non ci si può certo illudere di affrontare neppure i problemi informatici apparentemente più semplici. Ti basti sapere che esistono libri interi dedicati ai metodi di crivello.
  • Re: [C++] Calcolo del milionesimo numero primo

    Ma il crivello non consiste nel prendere un numero x e andare avanti di x posizioni eliminando così tutti i suoi miltipli e poi tornare all'inizio e prendere un altro numero e ripetere la stessa cosa? Questo è quello che ho letto prima di scrivere l'ultimo post
  • Re: [C++] Calcolo del milionesimo numero primo

    ANDPRI ha scritto:


    Ma il crivello non consiste nel prendere un numero x e andare avanti di x posizioni eliminando così tutti i suoi miltipli e poi tornare all'inizio e prendere un altro numero e ripetere la stessa cosa? Questo è quello che ho letto prima di scrivere l'ultimo post
    Devi imparare a documentarti meglio, a ragionare con più calma e soprattutto entrare nell'ordine di idee che, quando si ha la tua età e si frequenta un forum tecnico minimamente serio, quasi tutti gli scriventi (eccetto al più qualche coetaneo) conoscono un'infinità di cose che al momento neppure immagini. Certo, esistono anche "forum" da quattro soldi frequentati unicamente da lamer tredicenni con soprannomi leet che si atteggiano a guru della programmazione, ma è evidente che nessuno li prende davvero in considerazione, e sicuramente lì c'è ben poco da imparare...

    Ti stai fissando sull'idea di "multipli" come parenti di "moltiplicazione", il che è ovviamente una grossa ingenuità. Chissà cosa succede se in un qualsiasi spreadsheet, alla cella A2 si immette la formula "=A1+A$1" e la si copia in basso per una ventina di celle, immettendo poi in A1 un qualsiasi numero intero positivo a piacere... giusto per informazione, esiste una intera branca di teoria dei numeri che si chiama "" nella quale, pensa un po', si usa un'algebra in cui non servono le moltiplicazioni (e quindi non sono neppure definite, d'altronde una moltiplicazione non è che una serie predefinita di somme e l'elevamento ad esponente naturale non è che una serie di moltiplicazioni...).
    NB: Tale teoria fa il paio con la teoria combinatoria dei numeri, con la quale ha in comune alcuni elementi della geometria dei sumsets. Esiste addirittura una teoria additiva dei soli numeri primi.
  • Re: [C++] Calcolo del milionesimo numero primo

    Veramente non sono stato su nessun forum di lamer, ma su wikipedia, dove tra l'altro c'è pure scritto che non è un metodo efficiente
  • Re: [C++] Calcolo del milionesimo numero primo

    ANDPRI ha scritto:


    Veramente non sono stato su nessun forum di lamer, ma su wikipedia, dove tra l'altro c'è pure scritto che non è un metodo efficiente
    Altra cosa da apprendere subito: wikipedia, specialmente quella italiana, è peggio di un covo di lamer. E' un ottimo modo per prendere delle cantonate pazzesche, non esiste alcun controllo o revisione sulle voci da parte di esperti, chiunque può scrivere qualsiasi cosa.
    L'informatica è una scienza e come tale si studia sui migliori libri, come hanno fatto tutti i professionisti. Per documentarsi online occorrono anticorpi grossi come salmoni e capacità di selezione delle fonti che oggi si arriva a sviluppare seriamente solo dopo la laurea e/o durante la tesi di secondo livello.

    Ti è già stato spiegato in vari modi che il crivello è comunque molto più efficiente dei metodi di fattorizzazione naif che conosci, che sono in assoluto il peggior approccio possibile al problema su una architettura mainstream. Dunque è enormemente meglio della "soluzione" di OP e della tua. I crivelli additivi funzionano in O(N), gli algoritmi naive sono quadratici per ben che vada, non c'è proprio alcun confronto possibile. Lo si può dimostrare con quattro righe di conti usando l'algebra operazionale, ma tutto ciò purtroppo per te è arabo: puoi sempre studiare e cercare di capire il codice e le spiegazioni del thread che ti è stato indicato, notevolmente più serio e approfondito di wikipedia. Con un minimo di sforzo, anche se ciò esula totalmente da questo thread, i banali crivelli si possono ottimizzare in maniera notevole, come questo. Con buona pace degli asini di wikipedia, posto che comunque è ovvio e arcinoto che esistono metodi anche più efficienti per operazioni specifiche, come i test di primalità. In fondo, il crivello serve a creare una volta sola una tabella di primi, quindi in teoria potrebbe impiegare anche un paio di settimane. In realtà, qualsiasi versione minimamente ben implementata è sicuramente molto più efficiente dei 25 secondi riportati da OP, e ciò si può banalmente misurare, anche se si è totalmente all'oscuro del concetto di complessità big-O.

    Poi volendo possiamo anche parlare del test di primalità AKS o di quello di Rabin-Miller, ambedue ben al di là della portata del presente thread. Il problema rimangono sempre i limiti della tua preparazione e della tua capacità di comprensione, nonché le fonti inaffidabili delle quali credi di poterti avvalere per addirittura "discutere" con qualcuno enormemente più preparato di te che sta pazientemente cercando di farti capire qualcosa di importante.

    Dunque, smetti di insistere e di abusare della mia tolleranza: la questione è evidentemente al di là delle tue competenze attuali e sperare di venirne a capo leggendo quattro fregnacce su wikipedia serve solo a peggiorare la tua posizione di torto, sconfinando ormai nella mancanza di rispetto.
  • Re: [C++] Calcolo del milionesimo numero primo

    Ok
Devi accedere o registrarti per scrivere nel forum
10 risposte