Crivèl d'Eratostenes

Un article de Wikipèdia, l'enciclopèdia liura.
Salta a la navegació Salta a la cerca

Lo crivèl d'Eratostenes es un procés que permet de trobar totes los nombres primièrs inferiors a un certan entièr natural donat N. Es l'aujòl del crivèl d'Atkin qu'es mai aviat mai mai complèxe.

Algoritme[modificar | modificar la font]

L'algoritme fonciona per eliminacion: s'agís de suprimir d'una taula d'entièrs de 2 cap a N totes los multiples d'un entièr. Suprimissent totes los multiples, a la fin demora pas mai que los entièrs que son multiples de pas cap d'entièr, e que son doncas los nombres primièrs.

Començam per barrar los multiples de 2, puèi cada còp barram los multiples del mai petit entièr demorant.

Podèm s'arrestar quand lo carrat del mai petit entièr demorant es superior al mai grand entièr demorant, perque dins aquel cas, totes los nonprimièrs ja foguèron barrats de per abans.

A la fin del procés, totes los entièrs que foguèron pas barrats son los nombres primièrs inferiors a N.

L'animacion çaijós illustra lo crivèl d'Eratostenes per N=120 :

New Animation Sieve of Eratosthenes.gif