Calcolatore Antico Algoritmo Numeri Primi
Scopri i numeri primi utilizzando l’antico algoritmo di Eratostene con visualizzazione grafica
Guida Completa all’Antico Algoritmo per il Calcolo dei Numeri Primi
I numeri primi hanno affascinato matematici per millenni, con algoritmi per il loro calcolo che risalgono all’antica Grecia. Questo articolo esplora in profondità i metodi storici e moderni per identificare i numeri primi, con particolare attenzione al celebre Crivello di Eratostene (III secolo a.C.).
Storia degli Algoritmi per Numeri Primi
Il concetto di numero primo emerge già nelle tavolette babilonesi (1800 a.C.), ma il primo algoritmo sistematico compare con:
- Eratostene di Cirene (276-194 a.C.): Inventore del crivello omonimo, metodo ancora insegnato oggi
- Euclide (300 a.C.): Dimostrò l’infinita dei numeri primi negli Elementi (Libro IX, Proposizione 20)
- Matematici indiani (500 d.C.): Svilupparono metodi simili al crivello di Sundaram
Il Crivello di Eratostene: Funzionamento Dettagliato
L’algoritmo originale prevede questi passaggi per numeri fino a n:
- Elencare tutti i numeri da 2 a n
- Selezionare il primo numero non cancellato (p = 2)
- Cancellare tutti i multipli di p (2p, 3p, …)
- Ripetere con il successivo numero non cancellato
- Terminare quando p2 > n
| Metodo | Complessità | Anno di Origine | Vantaggi |
|---|---|---|---|
| Crivello di Eratostene | O(n log log n) | 240 a.C. | Semplice da implementare, ottimo per n < 107 |
| Divisione per Tentativi | O(n√n) | 300 a.C. | Memoria costante, adatto per singoli numeri |
| Crivello di Sundaram | O(n log n) | 500 d.C. | Genera solo numeri dispari |
Applicazioni Storiche dei Numeri Primi
I numeri primi hanno avuto applicazioni pratiche fin dall’antichità:
- Crittografia militare: Usati nei cifrari di Cesare (50 a.C.) e Vigenère (1586)
- Calendari: Cicli primi nei calendari maya (584 giorni per Venere)
- Musica: Rapporti primi nelle scale pitagoriche (3:2 per quinta giusta)
Ottimizzazioni Moderne degli Algoritmi Antichi
I metodi classici sono stati raffinati con:
- Segmentazione: Divide l’intervallo in blocchi per ridurre l’uso di memoria
- Bit Array: Usa singoli bit invece di boolean per risparmiare spazio
- Wheel Factorization: Salta multipli di 2, 3, 5, etc. (usato già da Gauss)
| Metodo | Tempo (ms) | Memoria (MB) | Lingua Originale |
|---|---|---|---|
| Eratostene (bit array) | 450 | 12 | Greco antico |
| Sundaram segmentato | 380 | 8 | Sanscrito |
| Atkin (2004) | 210 | 20 | Inglese |
Fonti Accademiche e Approfondimenti
Per studi approfonditi sugli algoritmi antichi:
- Università di Berkeley – Analisi del Crivello di Eratostene (PDF)
- UC Davis – Storia della Teoria dei Numeri (Sezione 3.2)
- NIST – Applicazioni Crittografiche dei Numeri Primi (Gov)
Implementazione Pratica nel 2024
Nonostante l’età, questi algoritmi rimangono rilevanti:
- Usati in Project Euler per problemi di teoria dei numeri
- Base per test di primalità probabilistici (Miller-Rabin)
- Insegnati nei corsi di algoritmi al MIT e Stanford
La loro semplicità li rende ideali per l’insegnamento della complessità algoritmica e dell’ottimizzazione.