calcolo dei numeri primi in c

Prima di proseguire...

Potrebbe interessarti la nostra collezione di esercizi C risolti?

Vediamo oggi due algoritmi per il calcolo dei numeri primi e vediamo come usando un pò più di ram si riesce ad ottimizzare di un bel po’ il programma.

Un modo semplice per il calcolo dei numeri primi di un numero è utilizzare una funzione che ogni volta controlla se un numero passato come parametro non è divisibile per nessuno dei numeri precedenti:

#include<stdio.h>
int primo(int num);
int main(){
 
//dichiarazioni
 
int i,num,prim=0;
 
//acquisizione dati
 
printf("inserire il numero fino al quale arrivare : ");
scanf("%d",&num);
 
//calcoli
for(i=0;i<=num;i++)
if(prim)
printf("%d\n",i);
}
 
int primo(int num){
int i;
 
for(i=2;i<num;i++)
if(num%i == 0)
return 0;
return 1;
}

Il codice dovrebbe essere abbastanza chiaro : la funzione primo controlla il resto del numero da verificare diviso per il numero di iterazione corrente e se è uguale a zero (cioè divisibile) ritorna 0 se no a fine iterazione ritorna 1.
Nel main invece non faccio altro che controllare per ogni numero minore di n se è primo(richiamando al funzione), se lo è lo stampo.

Ma in questo modo si fanno delle operazioni inutili, ad esemepio si sa già che basta controllare solo i numeri primi precedenti al numero e non fare i controlli ogni volta con tutti i numeri (anche quelli non primi).
Perciò è meglio memorizzarsi ogni volta i numeri primi trovati in un array, o meglio (per rendere l’algoritmo più generale possibile) in un area di ram allocata dinamicamente:

#include<stdio.h>
#include<stdlib.h>
long long *primi,ii=2;
int primo(long long num);
int main(){
    long long i, numeri;
    primi = (long long *)malloc(sizeof(long long));
    primi[0] = 2;
    printf("inserire il numero fino al quale arrivare : ");
    scanf("%lld",&numeri);
    for(i = 2;i<=numeri;i++)
        if(primo(i))
            printf("%lld\n",i);
             
    printf("numeri primi inferiori di %lld\n",numeri);
}
 
int primo(long long num){
    primi = (long long *)realloc(primi,sizeof(long long)*ii);
    long long i;
    int prim = 1;
    if(num == 2)
           return 1;
    for(i=0;i<ii-1;i++)
        if(num%primi[i] == 0)
            prim = 0;
     
    if (prim)
        primi[ii++-1] = num;
    return prim;
}

In questo codice invece il main rimane molto simile con la differenza che metto, all’inizio, prima alloco un byte e mi memorizzo l’indirizzo in un puntatore (primi) e poi metto all’inizio dell’area puntata da primi il valore 2, il primo numero primo.
Mentre la funzione primo cambia abbastanza :
Innanzitutto il rialloco la memoria, questa volta in uno spazio più grande di un byte, uguale a ii (variabile globale che vale 2); eseguo il controllo per verificare se è divisibile in modo iterativo con i numeri precedentemente trovati, i-1 volte ed infine se il numero è primo lo aggiungo allal fine dell’area di memoria puntata e ritorno inseguito se 1 se il numero era primo altrimenti 0.

La differenza tra i due algoritmi è; notevole:
per calcolare i numeri primi inferiori a 10000 il primo impiega 330s minuti mentre il secondo 37 s.
l’unico svantaggio del secondo è che occupa sempre più ram, ma sotto linux la quantità occupata dal programma è sempre poca e accettabile (al max qualche mega).
Il vantaggo di queste funzioni è che possono essere usate anche per il calcolo dei numeir non primi, smeplicemente negando il ritorno.

calcolo dei numeri primi in c by cardinale claudio is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.