Funzione per generare Numeri Primi – Codice VB.NET
Una funzione per generare numeri primi, tutti i numeri primi, entro un dato intervallo tramite codice VB.NET
I numeri primi affascinano senza dubbio; nel corso dei secoli migliaia di appassionati e studiosi matematici hanno cercato di carpirne il segreto e ottenere una funzione semplice ed elegante che generasse tutti i numeri primi esistenti. Nella programmazione avere un elenco di numeri primi può essere sia un semplice esercizio di studio di un algoritmo sia una reale necessità, dovendo ad esempio creare codici per la cifratura di documenti o altro. Ovviamente si potrà sia usare ogni volta una routine che li generi “al volo” oppure si potrà generarli una sola volta e salvarli in un file. La funzione che si occupa di generare numeri primi entro un dato intervallo e che viene ivi proposta è la seguente: IngAC_GENERA_NUMERI_PRIMI(Estremo_Inferiore As ULong, Estremo_Superiore As ULong) As ULong(). Qui di seguito il codice in linguaggio VB.NET che ovviamente è solo una delle tante possibili soluzioni al problema di generare numeri primi.
Function IngAC_GENERA_N_PRIMI(Estremo_Inferiore As ULong, Estremo_Superiore As ULong) As ULong()
' controlla di non eccedere il massimo valore ulong
If Estremo_Superiore > 1.84 * 10 ^ 19 Then Estremo_Superiore = 1.84 * 10 ^ 19
' controlla che l'inf sia al massimo pari al sup
If Estremo_Superiore < Estremo_Inferiore Then Estremo_Inferiore = Estremo_Superiore
' inizializzazione variabili
Dim Counter As ULong = 0
Dim Counter_Primi As ULong = 0
Dim Counter_Output As ULong = 0
Dim Ultimo_Primo As ULong = 0
Dim max_Numeri_Primi_output = (Estremo_Superiore - Estremo_Inferiore)
Dim up_MATRIX As ULong = Estremo_Superiore
Dim Numeri_Primi(up_MATRIX) As ULong
Dim Numeri_Primi_Output(max_Numeri_Primi_output) As ULong
Dim Produttoria As ULong = 1
Dim Counter_Upper As ULong = 0
' inizio ciclo for per cercare tutti i primi fino all'estr sup
For N As ULong = 2 To Estremo_Superiore
' resetta i contatori
Counter = 0
Counter_Upper = 0
Produttoria = 1
' calcola quanti numeri primi deve considerare
' tramite counter_upper
For KK As ULong = 0 To Counter_Primi
If (Produttoria > N) Then Exit For
Produttoria = Produttoria * Numeri_Primi(KK)
Application.DoEvents()
Counter_Upper += 1
Next
' controlla quanti divisori ha in numero N
' eccetto se stesso e l'uno
For M As ULong = 0 To Counter_Upper
If Numeri_Primi(M) > 0 Then
If (N Mod Numeri_Primi(M)) = 0 Then
Counter += 1
End If
End If
Application.DoEvents()
Next
' se non ci sono divisori per come definiti
' nel ciclo for allora è un numero primo
If (Counter < 1) Then
Ultimo_Primo = N
Numeri_Primi(Counter_Primi) = Ultimo_Primo
' riempie la matrice di output
If Numeri_Primi(Counter_Primi) >= Estremo_Inferiore Then
Numeri_Primi_Output(Counter_Output) = Ultimo_Primo
Counter_Output += 1
End If
Counter_Primi += 1
End If
' blocca il ciclo for se si supera l'indice massimo
If Counter_Primi > up_MATRIX Then Exit For
Next
' se sono stati trovati numeri primi ridimensiona la matrice di output
If Counter_Output > 0 Then
ReDim Preserve Numeri_Primi_Output(Counter_Output - 1)
End If
Return Numeri_Primi_Output
End FunctionAggiornamento e miglioramento della funzione
Si proceduto a una piccola modifica che fa più che dimezzare i tempi di ricerca dei numeri primi, semplicemente dal notare che essi sono tutti dispari, tranne il 2.
Dim Counter_Upper As ULong = 0
' inizio ciclo for per cercare tutti i primi fino all'estr sup
' i numeri da testare devono essere dispari tranne il primo (2)
Numeri_Primi_Output(0) = 2
Counter_Output = 1
For N As ULong = 3 To Estremo_Superiore Step 2
' resetta i contatori
Counter = 0Input e output della funzione per generare numeri primi
La funzione (sulla quale prossimamente verrà effettuato un overloading per avere N numeri primi a partire da un numero n fissato e un altro overloading con solo il limite superiore, n fissato) ha, attualmente due parametri di input:
- Estremo_Inferiore As ULong, che rappresenta il numero più basso -compreso- da cui cominciare a cercare numeri primi, e
- Estremo_Superiore As ULong, che ovviamente è il numero più alto entro cui cercare numeri primi.
La funzione, in output, restituisce una matrice contenente tutti i numeri primi compresi nell’intervallo [Estremo_Inferiore;Estremo_Superiore].
Descrizione della funzione e note
Per generare numeri primi. la funzione si basa sul secondo ciclo For … Next in cui avviene il controllo del rapporto dell’ n-esimo numero intero con l’elenco di tutti i numeri primi trovati fino a quel momento. Se questo rapporto da resto zero e se il contatore dei divisori (Counter) è zero, allora il numero è primo. Il resto della funzione si occupa di controllare i dati di input, inizializzare e tutti i contatori e creare le matrici necessarie; infine di restituire l’array ridimensionato contenente i numeri primi desiderati in base all’input. Ovviamente il tipo Ulong ammette solo valori positivi interi e ovviamente il tempo di calcolo e la quantità di numeri calcolabili è dipendente dal tipo di macchina su cui viene fatto girare il programma. Più sono grandi i numeri in ballo e maggiore sarà il numero di rapporti da controllare per il calcolatore. Con un portatile dotato di un i7 dual core @2,5Ghz e 16GB di RAM, per elaborare i numeri primi nell’intervallo da 0 a 1 milione occorrono 16 secondi circa. PS. con la modifica al codice proposta poco sopra i tempi passano a circa 6 secondi.
