Programmazione..quale incubo! Generiamo i numeri primi.

Eccoci di nuovo qui.
Nella nostra ultima lezione abbiamo generato i numeri della serie di Fibonacci. Ora vediamo come fare a generare i primi N numeri primi.
Ormai avete imparato quali sono le righe fondamentali da scrivere immediatamente:

program primi
implicit none

end program

Perfetto. Prima di tutto pensiamo a quale può essere un modo intuitivo per individuare i numeri primi, ricordandoci che tutti i numeri sono divisibili per 1 e per loro stessi. Allora, partiamo da 3 e vediamo se è divisibile per i numeri che lo precedono, cioè 2. Non lo è, quindi è primo. Andiamo con 4: 4 non è divisibile per 3 ma lo è per 2 e quindi lo togliamo. Vediamo 5: non è divisibile per 4, nè per 3, nè per 2 quindi è primo.
Ci siete?
Ora dobbiamo tradurre questo ragionamento in linguaggio fortran.
Sicuramente avremo bisogno di fare una divisione tra coppie di numeri per verificare se siano multipli o no giusto?
In fortran esiste una funzione che ci da il resto di una divisione tra 2 numeri:

mod(a,b)

Se questa funzione è diversa da 0, significa che a e b non sono multipli tra loro, altrimenti sì. Ricordiamoci che ad ogni funzione va associata una variabile, cioè

r=mod(a,b)

Ottimo. Naturalmente a e b varieranno perché dobbiamo controllare tutti i numeri fino ad un numero N che decidiamo noi: questo significa che dovrà esserci un ciclo, forse due.
Iniziamo: prima di tutto diciamo al programma quanti numeri primi vogliamo generare. Ricordiamoci che ogni variabile che inseriamo deve essere dichiarata.

program primi
implicit none
integer:: N
write(*,*) "Quanti numeri primi vuoi generare?"
read(*,*) N
end program

(Se non ricordate alcuni comandi, andate nei post precedenti).
Ho accennato al fatto che avremo due cicli: perché? Perché dobbiamo fare un confronto tra due numeri variabili. Per farlo dobbiamo prendere ogni numero a partire da 3 (1 e 2 sono i primi due numeri e sono primi "per definizione")

do i=3,N

e poi confrontarlo con tutti i numeri che lo precedono, a partire da 2 fino al numero subito prima che sarà (i-1)

do j=2,i-1

Quindi il secondo "do" sarà dentro al primo: così per i=3, confrontiamo 3 con j da 2 a (3-1) cioè solo con 2 in questo caso. Poi passiamo a i=4 e lo confrontiamo con j da 2 a (4-1)=3 ecc ecc.
Ricordiamoci che gli indici di un ciclo devono essere interi:

program primi
implicit none
integer:: N,i,j
write(*,*) "Quanti numeri primi vuoi generare?"
read(*,*) N
do i=3,N
do j=2,i-1
end do
end do
end program

Ok. E' il momento di inserire la funzione mod(a,b). Dove? Dentro al secondo "do" perché dobbiamo calcolarla per ogni coppia, giusto? Ricordiamoci di dichiarare sia la funzione che la variabile associata.

program primi
implicit none
integer:: N,i,j,mod,r
write(*,*) "Quanti numeri primi vuoi generare?"
read(*,*) N
do i=3,N
do j=2,i-1
r=mod(i,j)
end do
end do
end program

A questo punto dobbiamo controllare se il resto r è o no =0 e dirgli che se lo trova =0 deve uscire dal ciclo "j" e passare al numero "i" successivo; cioè, i=6 darà resto zero con j=3. A quel punto lui passerà ad analizzare i=7 perché 6 non è primo. Ci siamo?
Come facciamo a dire questo? In fortran c'è un comando con il quale diciamo: "se incontri questa condizione fai questa cosa".

if (condizione) then
istruzione
end if

Nel nostro caso sarà:

if (r==0) then
exit
end if

Gli abbiamo detto: se il resto è identico (per questo ci va il == e non solo =) a zero, esci dal ciclo.
Dove lo mettiamo? Dopo aver calcolato la funzione mod.


program primi
implicit none
integer:: N,i,j,mod,r
write(*,*) "Quanti numeri primi vuoi generare?"
read(*,*) N
do i=3,N
do j=2,i-1
r=mod(i,j)
if (r==0) then
exit
end if
end do
end do
end program

Bene. Però così non facciamo altro che uscire dal ciclo ogni volta che c'è un numero non primo. Noi vogliamo farci scrivere i numeri primi quando li trova. Allora dobbiamo mettergli un'altra condizione, cioè utilizzare un altro "if". Qual è questa condizione? Sicuramente che r sia diverso da zero ma capiamo che il controllo deve andare avanti fino ad un numero abbastanza vicino ad "i".
Mi spiego meglio: un numero dispari sicuramente non è divisibile per 2 ma noi non vogliamo che il programma si blocchi perché quel numero potrebbe essere divisibile per un numero successivo a 2. Allora dobbiamo dirgli:

if ((r/=0) .AND. (trigger=i-3)) then
write(*,*)'Ho trovato',i
end if

Cioè, se trovi che la funzione "mod" è diversa da zero (r/=0) e contemporaneamente (.AND. logico) siamo ad un numero "j" che equivale a i-3 (trigger=i-3), allora sta sicuro che quello è primo e scrivilo sul monitor.
Dato che questo "if" si aggiunge all' "if" precedente, il primo "if" non va chiuso e al posto del secondo "if" dovremo mettere "else if" (altrimenti se) e poi chiudere:

if (r==0) then
exit
else if ((r/=0) .AND. (trigger=i-3)) then
write(*,*)'Ho trovato',i
end if

La variabile "trigger" ci serve per contare il numero di cicli "j". All'inizio sarà =0 e poi aumenterà di uno ad ogni ciclo j:

trigger= trigger+1

Mettiamo questi concetti insieme:

program primi
implicit none
integer:: N,i,j,mod,r,trigger
write(*,*) "Quanti numeri primi vuoi generare?"
read(*,*) N
trigger=0
do i=3,N
do j=2,i-1
r=mod(i,j)
if (r==0) then
exit
else if ((r/=0) .AND. (trigger=i-3)) then
write(*,*)'Ho trovato',i
end if
trigger=trigger+1
end do
end do
end program

Avete creato un algoritmo che vi genere N numeri primi! Complimenti!