1.2.2 Eratosthenes si

$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 , kan man bruge en metode som går under navnet Eratosthenes si.

Man starter med at skrive alle tallene mindre end og større end 1 op efter hinanden. Sætter vi 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 , 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$

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