Elementare, caro dottor Watson...Originariamente inviata da fenics
Ma cosa dice codesto algoritmo, certo non efficientissimo ma di facilissima implementazione, nella sua versione di base "carta-e-penna"?
Fissato un limite arbitrario intero positivo n (significativamente maggiore di due), si compila una tabella contenente ordinatamente tutti i numeri interi positivi strettamente compresi tra 2 e tale n. Quindi, per ogni intero positivo strettamente compreso tra 2 e la radice quadrata di n (approssimata per difetto all'intero, ovviamente!) si "cancellano" dalla tabella tutti i multipli di tale numero.
I numeri rimanenti dopo questa "setacciatura" sono tutti e soli i numeri primi compresi tra due (primo numero primo e unico primo pari) e il limite dato.
Tutto chiaro fino a qui? Quel "per ogni" si traduce ovviamente in un ciclo, e "tutti i multipli" in un secondo ciclo annidato.
Prova intanto ad implementare questa parte, usando uno zero per "cancellare" i valori compositi dalla tabella: per migliorie e ottimizzazioni c'è tempo e modo di procedere per gradi (le due più banali e macroscopiche: i numeri pari possono subito essere esclusi per costruzione, e la "tabella" può essere facilmente implementata come un array grossolanamente booleano, sebbene in modo poco efficiente in spazio).
Rispondi quotando