Arduino alla ricerca dei numeri primi. Parte 2

Ciao e ben ritrovato sul Blog.
Oggi vi parlerò, con un po' più di calma, di come è stato sviluppato lo sketch pubblicato nello scorso articolo. Se non sai a cosa mi riferisco ti conviene iniziare leggendo l'articolo precedente per non confonderti.

Fig. 1 - Lo sketch per la ricerca dei numeri primi  di Paolo Luongo

Iniziamo con alcune premesse iniziali:

1. il programma calcola il numero di numeri primi (scusate il bisticcio di parole) e poi si ferma;
2.  non si devono aggiungere display e cose simili;
3.  l'argoritmo di ricerca (dei numeri primi) deve essere sufficientemente veloce.

Partendo dal secondo punto basta utilizzare la console seriale che fà parte dell'IDE di Arduino.
Per il primo punto non ci sono particolari problemi, basta osservare la soluzione in figura 2.

Fig. 2 - Main ed Altro - sketch di Paolo Luongo

Il programma principale (loop) è composto da due funzioni:

• CercaPrimi() che si occupa di trovare i numeri primi;
• Stop() che bloccherà il nostro Arduino all'infinito. Per sbloccarlo dovremo premere il pulsante di reset.

Per la funzione Stop() ero un pò restio alla sua realizzazione ma, viste le continue richieste, ho preferito mostrare come simulare l'alt di un µC semplicemente mettendolo in un ciclo senza fine. 

Non mi piace come soluzione,  ma è comunque adatta allo scopo: in generale un µP o µC va messo in sleep e non in un ciclo infinito, ma per adesso  ... va bene così.

Per quello che riguarda la funzione Setup() ho abilitato la console seriale, ho inviato un messaggio iniziale ed ho predisposto il LED sulla BOARD per il lampeggio (pin in uscita).

Ora conviene spendere due parole su alcune variabili globali ed alcuni settaggi che si trovano in Fig. 1:
la #define di VERO e FALSO è solo un gioco per Italianizzare i programmi.

La #define Stampa_Numeri va impostata a VERO se si vogliono conoscere i numeri sulla console e a FALSO in caso contrario.

Lo stesso discorso vale per Fai_Lampo se si vuole far lampeggiare il LED ogni volta che è stato trovato un numero primo.

Infine la costante Q ha il valore di quanti numeri primi si voglio conoscere.

Questa variabile ci porta al problema dell'algoritmo scelto che è ora di spiegare.

Basandomi sulla definizione di numero primo, che dice che un numero è primo quando è divisibile solo per 1 e per se stesso, si apre la porta ad un primo algoritmo. Preso un numero N lo si dividerà per tutti i numeri interi maggiori di 1 e minori del numero stesso (N-1). Nel caso in cui il resto di una divisione sia uguale a zero vorrà dire che quel numero è un divisore di N e quindi N non è un numero primo.

Messo in questi termini il procedimento non è proprio velocissimo ed una prima semplificazione può essere fatta con un piccolo corollario della definizione: ovvero lo si dividerà per tutti i numeri primi, minori di N. Si può ancora fare di meglio, ma è sufficiente per il momento.

Allora vediamo la parte del codice che ho scritto, in figura 3:

Fig. 3 - La funzione CercaPrimi() - sketch di Paolo Luongo

Un primo problema è stato: dove memorizzo i numeri primi via via che vengono trovati?

Semplice, in un vettore che, con grande fantasia, ho chiamato ElencoNumeriPrimi .

Il problema del vettore è che sfrutta la memoria RAM, che è piuttosto limitata in un µC.
Quindi con Arduino NANO ci dobbiamo fermare a 850 valori mentre con la MEGA 2560 possiamo arrivare a 3500.

Domanda: ma non possiamo fare di meglio? Con questo algoritmo non ne vale la pena: è sufficientemente veloce ma non è l'ideale per i microcontrollori (µC).

Tuttavia ho predisposto lo skecth per numeri più grandi definendo un tipo Tipo_Numero_Primo che ora è unsigned int ma si può facilmente cambiare in unsigned long. In questo modo il massimo numero primo passerà da un massimo di 65535 a oltre 2 Miliardi, precisamente 2³² meno 1 = 4294967295.

Per ovviare, vi mostrerò nella terza parte di questi articoli, un nuovo sketch che utilizza un algoritmo basato strettamente sulla definizione: sarà più lento ma avrà limiti più ampii. Ne riparleremo.

Fig. 4 - La funzione E Un Numero Primo ?  - sketch di Paolo Luongo

Resta la funzione EUnNumeroPrimo(), in Fig.4,  che si occupa di fare tutte le divisioni e si fermerà appena avrà trovato un numero divisore o avrà raggiunto il numero da esaminare.

Per ora mi fermo qui. In caso di dubbi ci sono le FAQ. Se preferisci scrivimi una email o commenta il post.

Ciao

Paolo

;-)