Eratostenovo sito

Eratostenovo sito je jednoduchý algoritmus, ktorý hľadá prvočísla v danom intervale. Algoritmus počíta s tým, že násobky prvočísel už nie sú prvočísla (sú deliteľné aj iným číslom).

Popis

Najskôr objasním prvočísla. Sú to čísla deliteľné len jednotkou a sama sebou. Avšak číslo jedna nie je prvočíslo, preto algoritmus hľadá od 2 do N. Ak by sme chceli nájsť všetky prvočísla v nejakom intervale bez Eratosthenova sita, museli by sme overovať, či dané číslo nie je deliteľné bezo zvyšku niektorým menším číslom, čo by bolo veľmi náročné. Tento algoritmus si ale "škrtá" všetky násobky prvočísel, a tak je podstatne rýchlejšia.

Máme napríklad rad čísel do pätnástich a vieme, že 2 je prvočíslo. Tým pádom všetky jeho násobky ktorej prvočíslami byť nemôžu, pretože sú už deliteľné dvojkou. Môžeme si ich teda vyškrtnúť

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15

Postup v bodoch

1. Načítame čísla v intervale od 2 do 15

Čísla: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15; Prvočísla: zatiaľ žiadna

1. Odoberieme prvé číslo (2) a uložíme ho ako prvočíslo.

Čísla: 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15; Prvočísla: 2

1. Odoberieme všetky násobky daného čísla (2) do 15

Čísla: 3, 5, 7, 9, 11, 13, 15; Prvočísla: 2

1. Urobíme to isté pre ďalšie číslo (3)

Toto opakujeme kým máme ešte čísla.

Vylepšenia algoritmu

Algoritmus môžeme ešte vylepšiť. Je totiž zbytočné prechádzať čísla až do dobrí hranice (ďalej len N). Môžeme ich prechádzať len do odmocniny z N. Ak totiž budeme mať číslo zapísané ako x * y, tak x a y bude vždy <= odmocnine z N.

Ukážka v céčko

#include <stdio.h>
#include <math.h>
#define N 100

int main()
{
  int cisla[N], i, j;
  for (i = 2; i < N; i++)
      cisla[i] = 1; // Není prvočíslo

  for (i = 2; i < sqrt(N); i++) {
      if (cisla[i] == 0) continue;
      for(j = 2*i; j < N; j += i)
          cisla[j] = 0;
  }

  for (i = 2; i < N; i++) {
      if (cisla[i] == 1)
         printf("%d\n", i);
  }
  getchar();
  return 0;
}

Ukážka v Jave

package algoritmy;

public class Sieve {

    private boolean[] cisla;

    public Sieve(int n) {
        cisla = new boolean[n];
        cisla[0] = cisla[1] = true;
        for(int i = 2; i < Math.sqrt(n); i++) {
            if (cisla[i] == true) continue;
            for (int j = 2*i; j < n; j += i)
                cisla[j] = true;
        }
    }

    public String toString() {
        String str = "";
        for(int i = 2; i < cisla.length; i++) {
            if (cisla[i] == false)
                str += i + ", ";
        }
        return str;
    }

    public static void main(String[] args) {
        Sieve eratosthenes = new Sieve(100);
        System.out.println(eratosthenes);
    }

}

Ukážka v C#

using System;

namespace Algoritmy
{
    class Sieve
    {
        private bool[] cisla;

        public Sieve(int n) {
            this.cisla = new bool[n];
            cisla[0] = cisla[1] = true;
            for (int i = 2; i < Math.Sqrt(n); i++)
            {
                if (cisla[i] == true) continue;
                for (int j = 2 * i; j < n; j += i)
                    cisla[j] = true;
            }
        }

        public String toString()
        {
            String str = "";
            for (int i = 2; i < cisla.Length; i++)
            {
                if (cisla[i] == false)
                    str += i + ", ";
            }
            return str;
        }
    }
}