next up previous contents
Næste: 1.3 Mersenne primtal Op: 1.2 At vise at Foregående: 1.2.1 Den naive metode


1.2.2 Eratosthenes si

Når man gerne vil finde alle primtal under en vis grænse $ g$, kan man bruge en metode som går under navnet Eratosthenes si.

Man starter med at skrive alle tallene mindre end $ g$ og større end 1 op efter hinanden. Sætter vi $ g=20$ får vi følgende talrække:

$\displaystyle 2, \hspace{0.5em} 3, \hspace{0.5em} 4, \hspace{0.5em} 5, \hspace{...
... 16, \hspace{0.5em} 17, \hspace{0.5em} 18, \hspace{0.5em} 19, \hspace{0.5em} 20$ (1.3)

Første tal på listen kan ikke have nogen ægte divisor, så 2 er derfor et primtal. Alle tal som 2 går op i har nu 2 som divisor, og er derfor sammensatte. Disse tal fjernes fra listen:

$\displaystyle 2, \hspace{0.5em} 3, \hspace{0.5em} 5, \hspace{0.5em} 7, \hspace{...
... 11, \hspace{0.5em} 13, \hspace{0.5em} 15, \hspace{0.5em} 17, \hspace{0.5em} 19$ (1.4)

Det næste tal i listen er 3, kan ikke have nogen ægte divisor. Hvis det havde, ville 3 ikke længere være i listen. Vi fjerner så alle tal som har 3 som divisor:

$\displaystyle 2, \hspace{0.5em} 3, \hspace{0.5em} 5, \hspace{0.5em} 7, \hspace{0.5em} 11, \hspace{0.5em} 13, \hspace{0.5em} 17, \hspace{0.5em} 19$ (1.5)

Vi kommer så til tallet 5. Men da $ 5^2=25>20$, behøver vi ikke at fortsætte. Hvis der var flere sammensatte tal under 20, kunne det jo ikke have et primtal mindre end 5 som faktor. Det mindste sammensatte tal vi kunne ``ramme'' ville altså være 25. Fordelen ved denne metode er, at vi finder mange primtal på én gang, ved at udføre næsten de samme beregninger som ved det første metode.


next up previous contents
Copyright © 2001, Martin Geisler.