calcolo dei numeri primi in c 5

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.