Az osztót miért csak a szám négyzetgyökéig érdemes keresni?

Mert az osztók párosával vannak.

Ha 'a' osztója 'n'-nek, akkor n/a is osztója.

Ezért az egyik mindig legfeljebb a gyöke lehet.

Pl 36 osztói

(1*36)

2*18

3*12

6*6

Mindegyik párban az első tagra igaz, hogy kisebb egyenlő, mint a szám gyöke.

Ha van egy p számod, ha ez összetett, akkor van olyan osztója ami nem nagyobb a gyökénél.

Ha a gyökéig nem találsz osztót, akkor p prím.

Nézzük a 16-ot:

1*16

2*8

4*4

8*2

16*1

A 4*4 (vagyis gyök 16) után semmi új infót nem kaptunk. Ugyanazok az osztók jöttek fel, csak fordítva.