Oblíbeným algoritmem začátečníků je elementární test prvočíselnosti, ve kterém se u testovaného čísla zkouší všichni jeho možní dělitelé a pokud žádný z nich nedělí toto číslo, pak jsme našli prvočíslo. Zarážkou, do které se testuje, je odmocnina z testovaného čísla, protože nejhorší možná situace, která může nastat, je, když má číslo jen dva dělitele a ti jsou totožní (odmocnina). Pokud by nebyli totožní, tak je jeden určitě menší a druhy větší než odmocnina a nám stačí ten nižší k jistotě, že to není prvočíslo. Pokud by bylo dělitelů více, tak je zřejmé, že tam najdeme menší číslo tím spíše.

Kód

    
    /**
     * Elementarni test prvociselnosti (deleni vsim do odmocniny)
     * @param nr cislo k testovani
     */
    public static boolean elementaryTest(int nr){
        if(nr <= 1) return false;
        if(nr == 2) return true;
        if(nr % 2 == 0) return false;
        for(int i = 3; i <= Math.sqrt(nr); i += 2){
            if(nr % i == 0) return false;
        }
        return true;
    }

/**
 * Elementarni test prvociselnosti (deleni vsim do odmocniny)
 * @param nr cislo k testovani
 */
bool elementaryTest(int nr){
    if(nr <= 1) return false;
    if(nr == 2) return true;
    if(nr % 2 == 0) return false;
    for(int i = 3; i <= sqrt((double)nr); i += 2){
        if(nr % i == 0) return false;
    }
    return true;
}

Rozbor

Pokud je číslo menší nebo rovno 1, tak prvočíslo není (1 není prvočíslo), pokud je sudé a není dva, tak také určitě není prvočíslo (2 je dělitelem). Pak už pouze stačí testovat všechna lichá čísla. Pokud žádné liché číslo do odmocniny není dělitelem, tak jsme našli prvočíslo.

Závěr

Tento algoritmus je velmi jednoduchý a také velmi neefektivní pro vysoká čísla, jakékoliv snahy o vylepšení tohoto algoritmu jsou marné, pro testy vysokých čísel (stovky míst (využití například v kryptografii)) se používají jiné testy (Solovay-Strassenův test, Rabin-Millerův test, Lehmannův test). Tyto testy sice nedávají odpověď s jistotou (100%), ale po provedení dostatečného počtu iterací se jejich přesnost ke 100% limitně blíží.