Il Crivello di Eratostene per Calcolatrice TI-84 Plus

Implementazione del crivello di Eratostene per calcolatrice TI-84 Plus

Proviamo ad implementare il crivello di Eratostene in TI-BASIC per la calcolatrice TI-84 Plus. Il crivello di Eratostene è un algoritmo che permette di trovare tutti i numeri primi minori di un certo numero $n$ .

Il programma sfrutta la lista $L_6$ per poter immagazzinare tutti i valori vero/falso relativi alla presenza di un numero primo. Inizialmente tutti i valori della lista sono impostati a vero, tranne quello relativo al numero 1 che è impostato a falso.

Le liste, per la calcolatrice TI-84 Plus, sono indicizzate a partire da 1 e possono contenere fino ad un massimo di 999 elementi. Per cui, il programma è in grado di calcolare i numeri primi fino a 999.

La lista $L_1$ , invece, viene utilizzata per memorizzare i numeri primi trovati.

La prima parte del programma, riportata di seguito, serve per inizializzare il tutto:

PROGRAM:CRIVELLO
:ClrHome
:Disp "Inserisci N:"
:Input "N=",N
:If N>999
:Then
:Disp "N troppo grande"
:Stop
:End
:N➔dim(L₆)
:Fill(1,L₆)
:0➔L₆(1)
:2➔P
:{2}➔L₁

La variabile $N$ rappresenta il numero massimo entro il quale cercare i numeri primi. Se $N$ è maggiore di 999, il programma si ferma e visualizza un messaggio di errore.

La lista $L_6$ viene inizializzata con tutti i valori impostati a vero, tranne il primo che è impostato a falso. La variabile $P$ viene inizializzata a 2 e la lista $L_1$ viene inizializzata con il primo numero primo, 2.

La seconda parte del programma, riportata di seguito, è il cuore dell'algoritmo:

:While (P≤√(N))
:For(I,P*2,N,P)
:0➔L₆(I)
:End
:P+1➔I
:While (I≤N) and (L₆(I)=0)
:I+1➔I
:End
:I➔P
:End

Il ciclo principale del programma continua finché il numero $P$ è minore o uguale alla radice quadrata di $N$ . All'interno del ciclo, per ogni numero $I$ multiplo di $P$ compreso tra $2P$ e $N$ , il valore della lista $L_6$ relativo a $I$ viene impostato a falso.

Alla fine di questa seconda parte, la lista $L_6$ conterrà tutti i valori vero relativi ai numeri primi minori o uguali a $N$ .

Rimane l'ultima parte, in cui, a partire dai valori contenuti in $L_6$ , vengono memorizzati i numeri primi trovati nella lista $L_1$ :

:For(I,3,N)
:If L₆(I)=1
:Then
:I➔L₁(1+dim(L₁))
:End
:End

Adesso, tutti i numeri primi minori o uguali a $N$ sono memorizzati nella lista $L_1$ . Per visualizzarla, basta andare nel menu statistico, premendo il pulsante stat e selezionando la voce 1: Edit....

Esempio di Esecuzione

Provando ad eseguire il programma CRIVELLO in questo modo:

**Figura 1:** Avvio del programma CRIVELLO sulla TI-84 Plus

La prima cosa che accade è la richiesta di inserire il valore di $N$ . In questo caso, abbiamo inserito il valore 120:

**Figura 2:** Input del Programma CRIVELLO

Dopo aver inserito il valore, il programma calcola tutti i numeri primi minori o uguali a 120 e li memorizza nella lista $L_1$ . Potrebbe volerci del tempo, soprattutto se inseriamo un valore di $N$ molto grande.

Quando il programma termina, la schermata che appare è la seguente:

A questo punto, come detto sopra, possiamo visualizzare il risultato andando nel menu statistico e selezionando la voce 1: Edit...:

**Figura 4:** Risultato del programma CRIVELLO

Tutti i numeri primi, fino a 120, saranno contenuti nella lista $L_1$ che possiamo scorrere da questo editor.

Torna alla lezione

Indice del capitolo