|
3. Due algoritmi di costruzione dei numeri primi
Dalla definizione di numero primo9
è possibile ricavare, fra gli altri, i due seguenti
algoritmi di costruzione di tutti i numeri primi in un intervallo prescelto
(0, N). Si tratta sempre di varianti del “crivello” di Eratostene,
varianti la cui scelta è arbitraria ed è solo suggerita
dalle necessità esposte nelle successive considerazioni.
1. |
In un intervallo prescelto (0,N) si fissino gli elementi dell’insieme
PP(2), vale a dire i nu-meri dispari; nello stesso intervallo, a
partire dal primo elemento maggiore di 2 di PP(2), che è
PP1(2) = 3, si fissino gli elementi dell’insieme
PP(3); nello stesso intervallo, a partire dal primo elemento maggiore
di 3 comune ai due insiemi PP(2) e PP(3), ossia appartenente a PP(2,3),
elemento che è PP1(2,3) = 5, si
fissino gli elementi dell’insieme PP[PP1(2,3)] = PP(5). Procedendo
allo stesso modo fino all’estremo superiore dell’inter-vallo,
sono stati individuati tutti i numeri primi dell’intervallo
stesso, costituiti da tutti i numeri PP1(2..n).10
|
2. |
In un intervallo prescelto (0,N), si fissino gli elementi dell’insieme
PP(2); nell’intervallo si eliminino ora tutti gli elementi
dell’insieme PP(2) che sono prodotti del suo primo ele-mento
p maggiore di 2 per se stesso e per tutti gli altri elementi
dell’insieme PP(2) mag-giori di p, ottenendo in tal
modo tutti e soli gli elementi di PP(2,3) nell’intervallo
(0,N); nell’intervallo si eliminino ora dall’insieme
PP(2,3) i prodotti del primo elemento q maggiore di 3 dell’insieme
PP(2,3) per se stesso e per tutti gli elementi dell’insieme
maggiori di q;11e
così via con r, s, ... x. Tutti
i numeri primi dell’intervallo sono individuati se x2<N
e y2>N, con y successivo
di x nell’insieme PP(2..n).12
|
L’algoritmo 2 in particolare indica che l’eliminazione progressiva
della primalità potenziale di elementi dell’insieme PP(2)
è per sua natura un processo annidato nel verso della divergenza,
dato che le serie delle eliminazioni successive corrispondono a multipli
dei residui delle elimi-nazioni precedenti.13
Gli algoritmi qui indicati di costruzione dei numeri primi sono facilmente
meccanizzabili con l’uso di tabelle o “batterie” di
elementi di dimensioni opportune e mediante una sola procedura applicata
ricorsivamente.14
9. |
Spesso si definisce il numero primo come
un numero divisibile solo per se stesso e per l’unità.
Si tratta di una definizione vuota, dato che la divisione di un
numero per se stesso ri-definisce l’unità e la sua
divisione per l’unità ri-definisce il numero stesso.
Sembra quindi più ragionevole definirlo come numero intero
positivo che non è il prodotto di numeri interi positivi
compresi fra l’unità e il numero stesso. |
10. |
L’Appendice 1 ne dà una
visualizzazione immediata. |
11. |
Tutti i prodotti di q per p e per elementi
minori di p sono già stati eliminati nei passi precedenti.
|
12. |
Infatti le eliminazioni di numeri potenzialmente
primi per effetto del ciclo y avranno inizio solo con y
al quadrato; si vedano nel seguito le proprietà degli
insiemi PP(). Questo algoritmo è rappresentato mediante tabelle
e discusso nell’Appendice 2.
|
13. |
Residui che appartengono tutti all’insieme
PP(2,3) e, come ovvio, anche all’insieme PP(2). L’insieme
PP(2,3) è il più significativo perché è
l’ultimo dotato di ciclicità “perfetta”.
La dipendenza di ogni elemento di PP(2..n) dalla “storia”
di tutti gli elementi dei PP(2..m) di ordine inferiore
configura un sistema fondato su memoria, detto anche sistema dinamico,
quindi non predittivo per ragioni ovvie, anche se l’algoritmo
di costruzione è in sé invariante.
|
14. |
L’unico limite pratico è
la dimensione delle tabelle o “batterie” (array). Del
resto, per definizione stessa di numero pri-mo, ossia a causa della
natura dinamica e invariante della sua formazione, ogni possibile
metodo di costruzione dei numeri primi di un certo intervallo è
necessariamente basato su array e su un’unica procedura applicata
ricorsivamen-te.
|
|