Bármelyik számról megállapítható, hogy prímszám-e, ha csak a négyzetgyökénél kisebb osztókra vizsgálom?

Igen mindig elég a gyökéig vizsgálni.

De az nem pontos, hogy a gyökénél kisebb számokra vizsgálod, hanem a nem nagyobbakra kell.

pl 9 esetén a gyöke 3. Ha csak a 3-nál kisebbekre vizsgálod, akkor prímnek fog látszódni.

És nem kell az összes számmal végigosztani a gyökéig, elég csak a prímekkel.

Tehát pl. 101 esetén a 2-10-ig 9 db osztás helyett elég a 2,3,5,7 osztókkal.

Továbbá, ha nem prím akkor elég az első osztható számig vizsgálni.

Ha a négyzetgyökéig nincs osztója akkor azután sem lesz, hiszen ha létezik négyzetgyökénél nagyobb osztója akkor ez négyzetgyökénél kevesebb szerese kell hogy legyen aminek szintén osztója kell hogy legyen (a kettő szorzata kiadja a számot). Olyan szám nincs aminek csak négyzetgyökénél nagyobb osztója van, hiszen bármely 2 szám mely nagyobb a négyzetgyökénél a szorzatuk mindig nagyobb mint a szám.