Verificare se un numero è primo o meno

[Actarus5]

Riprendo la discussione cominciata qui per non continuare ad andare OT di là, comunque per come ho inteso io la richiesta immagino si aspettassero una funzione che prende in ingresso un numero e restituisce true se primo, false altrimenti, quindi non credo che un crivello sia adatto, io avrei scritto qualcosa del genere, a meno di usare una lookup table per i primi n primi:

Codice: Seleziona tutto

bool is_prime(uint64_t n)
{
    if(n <= 3)
    {
        return n > 1;
    }

    if((n % 2) == 0 || (n % 3) == 0)
    {
        return false;
    }

    for(uint64_t i = 5; (i * i) <= n; i += 6)
    {
        if((n % i) == 0 || (n % (i + 2)) == 0)
        {
            return false;
        }
    }

    return true;
}

Ovviamente non è un algoritmo di mia invenzione, però è molto più veloce del metodo naive che controlla tutti i divisori sino alla radice quadrata di n, lo spiegone si trova ad esempio qui.

[crap0101]

ehhh.., di là a un certo punto si è cominciato a parlare di crivelli certo non sono l'ideale per testare se uno specifico numero è primo (come vedi anche nei codici postati, tante robe sono ignorate)... poi si è divagato nella divagazione ed era interessante vedere come modificarlo per renderlo più efficace (almeno, per per come l'ho vista io).
Ho aggiornato il gist mettendoci anche questa versione (quella in python, ovviamente).

Anche gli altri metodi che elenca sono interessanti, seppur non tutti (benchè veloci) danno la sicurezza di aver effettivamente beccato un numero primo :-)

...può essere interessante verificare quale dei due metodi (e fino a che punto) è più rapido nel calcolarli tutti fino a un certo limite

[gila75]

Si, il crivello ho sbagliato io. Non e' adatto a testare un singolo numero, mea culpa