Elementární test prvočíselnosti

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.

    
    /**
     * 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íží.

{ zpětná vazba }

Tweet	Delicious
Sdílet

Hodnocení (0): 0

Přečtěte si také

Lehmannův test

Rabin-Millerův test

Diskuse

Pavel Mička19.3.2011

Souhlasím, v tomto případě si ale dovolím ponechat původní verzi s odmocninou. Jednak je to algoritmus, který často programují začátečníci a takto je více transparentní, za druhé je tato implementace stejně v reálném světě výkonnostně nepoužitelná, ať se použije kterákoliv varianta... (co se týká meditace nad (ne)přesností floatu, tak v tomto případě na tom nesejde...)

Ale rozhodně dobrá připomínka :-).

Wolda18.3.2011

Jen na okraj, rozhodne nez testovat podminku, zda i <= sqrt(nr) , je lepsi testovat ekvivalentni podminku i*i <= nr. Tim se totiz vyhneme nutnosti pouzivat float cisla, coz vyjma rychlosti umoznuje nemeditovat nad tim, zda nam pouziti floatu nezanasi nejakou chybu. Viz.

double x = sqrt(23);
if (x*x == 23) printf("Y"); else printf("N");

Co myslite, ze program odpovi? :-)

H.