Eratosthenovo síto (Eratosthenesz Kyrény, 276 až 194 př. n. l.) je jednoduchý algoritmus pro vyhledání prvočísel ležících v určitém intervalu. Základním principem algoritmu je fakt, že po nalezení prvočísla lze ze seznamu potenciálních prvočísel vyškrtnout všechny jeho násobky.

Princip Eratosthenova síta

Princip Eratosthenova síta

Množinu prvočísel nejprve algoritmus inicializuje na všechna přirozená čísla od 2 do N, kde N je horní hranice vyhledávání. Algoritmus pak v každém kroce vezme první prvek ze seznamu, označí jej jako prvočíslo a odebere z něj i všechny jeho násobky. Algoritmus pokračuje do té doby, než je seznam prázdný.

  1. Pracovní seznam = všechna přirozená čísla od 2 do N, kde N je horní hranice vyhledávání
  2. Množina prvočísel = prázdná množina
  3. Pro první prvek t z pracovního seznamu:
    1. Přidej prvek t do množiny prvočísel.
    2. Z pracovního seznamu odeber všechny jeho násobky (t, 2t, 3t...).
  4. Opakuj algoritmus od bodu 3, dokud není pracovní seznam prázdný.

Příklad

Zkusíme najít všechna prvočísla menší než 20.

KrokPracovní seznamOdstraněná číslaMnožina prvočísel
12, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20-(prázdná)
23, 5, 7, 9, 11, 13, 15, 17, 192, 4, 6, 8, 10, 12, 14, 16, 18, 202
35, 7, 11, 13, 17, 193, 9, 152, 3
47, 11, 13, 17, 1952, 3, 5
511, 13, 17, 1972, 3, 5, 7
613, 17, 19112, 3, 5, 7, 11
717, 19132, 3, 5, 7, 11, 13
819172, 3, 5, 7, 11, 13, 17
8-192, 3, 5, 7, 11, 13, 17, 19

Implementace (Java)

private static List<Integer> findPrimes(final int upperBound) {
    // čísla má smysl testovat pouze do druhé odmocniny horní meze

    final int upperBoundRoot = (int) Math.sqrt(upperBound);

    // true = je prvočíslo
    // false = není prvočíslo

    final BitSet isPrime = new BitSet(upperBound);

    // všechna čísla kromě 0, 1 nejprve označíme jako potenciální prvočísla

    isPrime.set(2, upperBound);

    for (int testedPrime = 2; testedPrime <= upperBoundRoot; testedPrime++) {
        if (isPrime.get(testedPrime)) {
            for (int testedPrimeMultiple = 2 * testedPrime;
                 testedPrimeMultiple <= upperBound;
                 testedPrimeMultiple += testedPrimeMultiple) {
                isPrime.clear(testedPrimeMultiple);
            }
        }
    }

    // pouze sesbírá všechna označená prvočísla do seznamu

    final List<Integer> primes = new LinkedList<>();

    int index = 0;

    while (index != -1) {
        index = isPrime.nextSetBit(index + 1);
        primes.add(index);
    }

    return primes;
}

Reference