promotion image of download ymail app
Promoted

Qualche genio di informatica!! mi sa dire se il crivello di Eratostene è più efficiente del mio programmino C?

ho fatto un programma che restituisce i numeri primi minori di un dato N immesso da tastiera.

lo fa controllando che il resto non sia zero dividendo ogni numeri da 2 a N per i numeri primi da 2 a radice di N. Ci sono stato 2 ore per calcolarne 6milioni... fino ai numeri ....99999959, 99999971, 99999989.

il bello è che via via che analizza il successivo, se è primo lo registra in un array e poi sono solo i numeri primi memorizzati nell'array che vengono usati per provare se saranno primi i successivi ancora..

5 risposte

Classificazione
  • 6 anni fa
    Risposta preferita

    Un sistema più efficiente è usare il cosiddetto "piccolo teorema di fermat" cioè che se x è un numero primo a^x - a è divisibile per x.

    Facendo questo giochino con a=2, a=3, a=4 e a=5 ti togli gran parte del lavoro e vai a fare il test fino in fondo solo per gli altri.

    Anche solo usando a=2 per i numeri fino a 2 miliardi ti ritrovi a fare il duro del lavoro per niente solo per 2000.

    Il problema è che con nummeri maggiori di 2^64 la precisione va a farsi benedire quindi ti servirebbe una libreria large numbers (che usa le stringhe) ma diventa troppo complicato.

    Il tradeoff è il classico velocità/memoria.

    Se vuoi minimizzare l'uso di memoria:

    #include <stdio.h>

    #include <math.h>

    int IsPrime(unsigned int x){

    unsigned int i;

    for(i=2;i<=sqrt(x);i++){

    if(x%i==0) return 0;

    }

    return 1;

    }

    int main(){

    unsigned int N;

    printf("Inserisci un numero: "); scanf("%u",&N);

    unsigned int i;

    printf("\nNumei Primi Inferiori a %u:",N);

    for(i=2;i<N;i++){

    if(IsPrime(i)) printf("\n%u",i);

    }

    printf("\nPremere invio per terminare...");getchar(); //Mette in pausa

    return 0;

    }

    Il setaccio invece usa la memoria massicciamente per aumentare la velocità. Per N = 1 miliardo il setaccio usa circa 4GB di RAM

    #include <stdio.h>

    #include <stdlib.h>

    int main(){

    unsigned int N;

    printf("Inserisci un numero: "); scanf("%u",&N);

    unsigned int *Vettore=(unsigned int *) calloc ((N-2),sizeof(unsigned int));

    unsigned int i,currentcount;

    printf("\nNumei Primi Inferiori a %u:",N);

    for(i=2;i<N;i++){

    if(Vettore[i-2]>0) continue;

    printf("\n%u",i);

    for(currentcount=2; i*currentcount<N; currentcount++){

    Vettore[(i*currentcount)-2]=1;

    }

    }

    free(Vettore);

    printf("\nPremere invio per terminare...");getchar(); //Mette in pausa

    return 0;

    }

    @cronos:

    Purtroppo per come è strutturata la memoria è impossibile far occupare meno di un byte a una variabile (quindi 4 miliardi sono poco meno di 4GB) per usare un solo bit ci vuole un po' più di lavoro:

    #include <stdio.h>

    #include <stdlib.h>

    #include <math.h>

    int main(){

    unsigned int N;

    printf("Inserisci un numero: "); scanf("%u",&N);

    unsigned char *Vettore=(unsigned char *) calloc (((N-2)/8)+ (N-2)%8==0 ? 0:1 ,sizeof(unsigned char));

    unsigned int i,currentcount;

    printf("\nNumei Primi Inferiori a %u:",N);

    unsigned char Birillo;

    for(i=2;i<N;i++){

    Birillo=1 << (i-2)%8;

    if((Vettore[(i-2)/8] & Birillo)) continue;

    printf("\n%u",i);

    for(currentcount=2; i*currentcount<N && (currentcount< 0xffffffffU/i); currentcount++){

    Birillo=1 << ((i*currentcount)-2)%8;

    Vettore[((i*currentcount)-2)/8] = Vettore[((i*currentcount)-2)/8] | Birillo;

    }

    }

    free(Vettore);

    printf("\nPremere invio per terminare...");getchar(); //Mette in pausa

    return 0;

    }

    Questo è un cesello che usa un solo bit a numero e, in termini di memoria, è il massimo dell'ottimizzazione.

    In pratica un numero x è primo se:

    (Vettore[x/8] & (1 << x%8)) == 0

    Tutti i primi inferiori al massimo unsiged int (4'294'967'295) occupano 511MB con questo sistema. In compenso per calcolare i numeri primi inferiori a 100'000'000 (senza stamparli a video) ci impiega poco più di 2 secondi sul mio PC, poco più di 4 secondi per salvarli su file e poco meno di 7 minuti per stamparli alla console.

    Edit 2:

    Ho provato anche ad implementare una versione del piccolo teorema di fermat a base 2.

    Non batte il cesello ma è abbastanza efficiente se devi controllare se un singolo numero è primo

    #include <stdio.h>

    #include <math.h>

    char FermatTest(unsigned int a){

    if(a==0xffffffffU) return 0; /*2^32 -1 non è primo*/

    unsigned int CountDigits;

    unsigned int divisor=a; unsigned int Numerator=0xffffffffU;

    for(CountDigits=0; (a >> CountDigits)>0 ;CountDigits++){}

    Numerator>>=32-CountDigits;

    divisor-=CountDigits;

    while(divisor>0){

    Numerator-=a;

    while(Numerator<a && divisor>0){

    Numerator<<=1;

    Numerator|=1;

    divisor--;

    }

    }

    Numerator-=1;

    if(Numerator>=a) Numerator-=a;

    if(Numerator!=0) return 0;

    for(CountDigits=2U; CountDigits<sqrt(a); CountDigits++){

    if(a%CountDigits==0) return 0;

    }

    return 1;

    }

    int main(){

    unsigned int N;

    printf("Inserisci un numero: "); scanf("%u",&N);

    printf("\nIl numero %u%se' primo:",N,FermatTest(N) ? " ":" non ");

    printf("\nPremere invio per terminare..."); getchar(); //Mette in pausa

    return 0;

    }

    • Commenter avatarAccedi per rispondere alle risposte
  • cronos
    Lv 6
    6 anni fa

    il crivello è decisamente più efficente del tuo metodo. per calcolare i numeri primi da 2 a 4 miliardi ci mette mezzo minuto (solo il calcolo, senza la visualizzazione che prende molto tempo). per quanto riguarda la RAM, un crivello fino a 4 miliardi usa mezzo gigabyte si ram avendo l'accortezza di usare un solo bit per i numeri da setacciare. infatti basta un solo bit per memorizzare i due stati del numero (cancellato / non cancellato)

    • Commenter avatarAccedi per rispondere alle risposte
  • 6 anni fa

    Ragazzi grazie a tutti per le risposte... specialmente le ultime due hehaheha cmq... cronos, può darsi che il mio ci metta molto per via del fatto che gli ho fatto stampare tutti i numeri uno sotto laltro (e anche il posto e fino a quale primo si ferma il ciclo di divisioni per ciascuno)? per salvare l&#x27;array in un file ci sta 3 secondi. Puo darsi che per calcolare senza stampare ci stia molto meno... e... cmq il file.dat che esce pesa 50megabyte..

    • Commenter avatarAccedi per rispondere alle risposte
  • 6 anni fa

    Ciao, è facile eseguire il confronto, non serve nemmeno chiedere. Costruisci il programma che implementa il crivello di Eratostene, lo fai eseguire e verifichi quanto tempo ci mette rispetto al tuo. Magari, prima, prova con qualche numero più piccolo, ad esempio fino a 10 mila.

    Mi sa che se continuerai a cercare con questo ritmo tra poco non ci saranno più numeri primi... o forse qua mi sto sbagliando ?

    • jolly6 anni faSegnala

      diciamo che sul fatto che siamo infiniti i numeri primi è da secoli ch nn ci sono dubbi.. per esempio il piu grande calcolato ora ha 17milioni di cifre... ... qua si parla di 9 cifre tipo..

    • Commenter avatarAccedi per rispondere alle risposte
  • Che ne pensi delle risposte? Puoi accedere per votare la risposta.
  • Anonimo
    6 anni fa

    ma che fai??? così ci metti una vita, prova ad usare il teorema di falloppio, quello di eustachio non funziona molto bene.

    • Commenter avatarAccedi per rispondere alle risposte
Altre domande? Fai una domanda e ottieni le risposte che cerchi.