Næste: 1.2.2 Eratosthenes si Op: 1.2 At vise at Foregående: 1.2 At vise at

1.2.1 Den naive metode

Det simpleste er at prøve at finde en faktor til tallet $n$ ved division. Sætning 1.2 siger, at hvis vi kan finde en ægte divisor til tallet $n$, så er $n$ ikke et primtal. Kan vi omvendt vise, at der ikke findes nogen ægte divisorer, så er tallet et primtal.

Så vi starter med at prøve at dele med 2, og hvis det ikke går op, prøver vi med 3, 4, 5 osv. Vi behøver kun at prøve indtil $i^2 \ge n$, hvor $i$ er det tal vi prøver med, da tal derover ikke vil kunne gå op i $n$. Hvis $ij=n$, hvor $i^2 \ge n$, må $j \le i$, men så er $j$ allerede testet.

Da man skal prøve med tal indtil $i^2 \ge n$, bliver beregningstiden meget stor, når vi arbejder med store tal. Allerede i antikken havde man derfor fundet en mere effektiv metode kaldet Eratosthenes si.