Ottenere i numeri primi

Posted on 2 giugno 2021. Filed under: Senza categoria |

Con questo articolo inizia una serie di articoli su come risolvere i problemi matematici grazie all’aiuto dell’informatica e della programmazione e come applicare la matematica nell’informatica.

La matematica è una dei miei tanti hobby e risolvere problemi ed equazioni nei giorni di festa mi rilassa.

Oggi vediamo i numeri primi.

Come abbiamo imparato a scuola, il numero primo è un intero positivo maggiore di 1 divisibile solo per sé stesso e per 1.

Questi sono numeri primi:  3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 e così via.

Fin dall’antichità i grandi matematici cercarono di ottenere un metodo di calcolo veloce e preciso.

In questo articolo useremo il Crivello di Eratostene, scritto dal matematico, astronomo, poeta, filosofo e geografo greco Eratostene di Cirene (276 a.C. – 194 a.C.).

Il Crivello di Erastotene è un antico algoritmo per il calcolo delle tabelle di numeri primi fino a un certo numero prefissato.

Il procedimento è il seguente: si scrivono tutti i numeri naturali a partire da 2 fino n in un elenco. Poi si cancellano tutti i multipli del primo numero dell’elenco (escluso lui stesso). Si prende poi il primo numero non cancellato maggiore di 2 e si ripete l’operazione con i numeri che seguono, proseguendo fino a che non si applica l’operazione all’ultimo numero non cancellato. I numeri che restano sono i numeri primi minori o uguali a n.

Vediamo quindi di tradurre tutto questo in codice, io lo scrivo in VB.NET ma voi potete convertirlo facilmente in un altro linguaggio.

Questo elenco per noi sarà un vettore, un array. Se ad esempio vogliamo scrivere i numeri primi fino a 30 scriveremo a partire dal numero 2 fino a 30 in questo array.

Andiamo poi a tirare via tutti i multipli di 2 (i numeri pari non saranno mai primi perché divisibili per 2) escluso lo stesso 2.

La nostra lista diventa quindi 3,5,7,9,11,13,15,17,19,21,23,25,27,29

 

Dobbiamo ora eliminare i multipli di 3, quindi la lista diventerà: 2,3,5,7,11,13,17,19,23,25,29

Dobbiamo ora eliminare i multipli di 5, quindi la lista diventerà: 2,3,5,7,11,13,17,19,23,29

Dobbiamo ora eliminare i multipli di 7 ma non ce ne sono, quindi la lista sarà così.

Anziché andare a togliere, noi nell’array ci metteremo solo i numeri che non sono multipli dei precedenti.

Da 1 a 10 dobbiamo fare la verifica che non sia multiplo di 2, di 3, di 5 e di 7. Il 4, il 6, l’8 e il 9 non saranno considerati essendo già loro multipli di 2 (2 * 2= 4; 2 * 3 = 6; 2 * 4 = 8), e di 3 (3 * 3 = 9)

 

Vediamo il tutto con il codice. Ho creato 3 tipi di esempi:

1) Quanti numeri primi vogliamo visualizzare.

Questo è il codice:

        Dim numeri As Integer = 10 ‘QUANTI NUMERI PRIMI VOGLIO TROVARE
        Dim cur As Integer = 3
        Dim divisore As Integer
        Dim RadiceQuadrata As Integer
        Console.WriteLine(2)
        For a = 1 To numeri – 1
inizio:
            RadiceQuadrata = Math.Sqrt(cur)
            For divisore = 3 To RadiceQuadrata Step 2
                If (cur Mod divisore) = 0 Then
                    ‘quindi aumento di due il numero analizzato
                    ‘(ottenendo il numero disperi successivo)
                    cur += 2
                    ‘e ricomincio ad analizzare
                    GoTo inizio
                End If
            Next

            ‘se il risultato di nessuna divisione da 0
            ‘il numero è primo
            Console.WriteLine(cur)
            cur += 2

        Next

 

E questo il risultato:

 

image

 

2) Fino a quale numero voglio arrivare a sapere se è primo:

Questo è il codice:

        Dim numeri As Double = 99999999999999999 ‘QUANTI NUMERI PRIMI VOGLIO TROVARE
        Dim numero As Integer = 50 ‘FINO A QUALE NUMERO VOGLIO TROVARE NUMERI PRIMI
        Dim cur As Integer = 3
        Dim divisore As Integer
        Dim RadiceQuadrata As Integer
        For a = 1 To numeri – 1
inizio:
            RadiceQuadrata = Math.Sqrt(cur)
            For divisore = 3 To RadiceQuadrata Step 2
                If (cur Mod divisore) = 0 Then
                    ‘quindi aumento di due il numero analizzato
                    ‘(ottenendo il numero disperi successivo)
                    cur += 2
                    ‘e ricomincio ad analizzare
                    GoTo inizio
                End If
            Next

            ‘se il risultato di nessuna divisione da 0
            ‘il numero è primo
            If cur >= numero Then Exit For

            Console.WriteLine(cur)
            cur += 2
        Next

 

E questo il risultato:

image

 

3) Il numero xxx è primo o no?

In questo caso non andremo a cercare i numeri primi, ma semplicemente dato un certo numero, si tratta di calcolare se è primo no.

Il codice è questo:

Dim cur As Integer = 37 ‘NUMERO DA CAPIRE SE è PRIMO O NO
Dim divisore As Integer
Dim RadiceQuadrata As Integer
Console.WriteLine(2)
Dim NumeroPrimo As Boolean = False
RadiceQuadrata = Math.Sqrt(cur)
For divisore = 3 To RadiceQuadrata Step 2
    If (cur Mod divisore) = 0 Then
        NumeroPrimo = False
        Console.WriteLine(cur & " non è un numero primo.")
        Exit Sub
    End If
Next

‘se il risultato di nessuna divisione da 0
‘il numero è primo
NumeroPrimo = True
Console.WriteLine(cur & " è un numero primo.")

 

E questo il risultato:

image

 

Proviamo con altri numeri:

image

 

Sicuramente il codice si potrà migliorare, ma non è lo scopo dell’articolo. Lo scopo dell’articolo era capire come funzionano i numeri primi e come ottenerli. Ci sono anche altri metodi per ottenere numeri primi, la prima procedura che mi è venuta in mente è questa.

Vedremo eventualmente in successivi articoli come usare altri metodi.

Per ora è tutto.

Make a Comment

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Liked it here?
Why not try sites on the blogroll...