Il Crivello di Eratostene per Calcolatrice CASIO FX-CG50

Implementazione del crivello di Eratostene per calcolatrice CASIO FX-CG50

Proviamo ad implementare il crivello di Eratostene in CASIO-BASIC per la calcolatrice CASIO FX-CG50. 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 L1 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.

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

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

"Inserisci N"↲
?➔N↲
N➔Dim List 1↲
Fill(1,List 1)↲
0➔List 1[1]↲
2➔P↲

La variabile $N$ rappresenta il numero massimo entro il quale cercare i numeri primi.

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

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

While P≤√N↲
For 2✕P➔I To N Step P↲
0➔List 1[I]↲
Next↲
For 1+P➔I To N↲
If List 1[I]=1↲
Then Break↲
IfEnd↲
Next↲
I➔P↲
WhileEnd↲
2➔J↲
1➔Dim List 2↲
2➔List 2[1]↲
For 3➔I To N↲
If List 1[I]=1↲
Then I➔List 2[J]↲
J+1➔J↲
IfEnd↲
Next↲
"Numero di primi"↲
J-1

Il ciclo principale del programma è un ciclo While che continua finché $P$ è minore o uguale alla radice quadrata di $N$ . All'interno del ciclo, viene eseguito un ciclo For che segna come falso tutti i multipli di $P$ nella lista L1. Successivamente, viene cercato il prossimo numero primo incrementando $I$ fino a trovare un valore in L1 uguale a 1.

Dopo aver trovato il prossimo numero primo, viene eseguito un ciclo For per memorizzare i numeri primi trovati nella lista L2.

Alla fine del programma, viene visualizzato il numero di numeri primi trovati.

Esempio di utilizzo

Supponiamo di voler trovare i numeri primi minori di 100.

Proviamo ad eseguire il programma dalla lista dei programmi premendo F1 e selezionando il programma SIEVE come mostrato nell'immagine sottostante:

**Figura 1:** Avvio del programma SIEVE sulla Calcolatrice CASIO fx-cg50

A questo punto, il programma chiede di inserire il numero $N$ . Inseriamo 100 e premiamo EXE.

Il programma termina e mostra il numero di numeri primi trovati, che in questo caso è 25.

A questo punto, possiamo visualizzare i numeri primi memorizzati nella lista L2 premendo premendo MENU e selezionando Statistics come mostrato nell'immagine sottostante:

**Figura 3:** Selezione dell'Applicazione Statistics

A questo punto, selezioniamo 1: List e poi 2: List 2 per visualizzare i numeri primi trovati:

Scorrendo la lista List 2, possiamo vedere tutti i numeri primi minori di 100.

Torna alla lezione

Indice del capitolo