Eratosthenovo síto

Algoritmy Matematické Eratosthenovo síto

Eratosthenovo síto je jednoduchý algoritmus, který hledá prvočísla v daném intervalu. Algoritmus počítá s tím, že násobky prvočísel již nejsou prvočísla (jsou dělitelná i jiným číslem).

Popis

Nejdříve objasním prvočísla. Jsou to čísla dělitelná jen jedničkou a sama sebou. Avšak číslo jedna není prvočíslo, proto algoritmus hledá od 2 do N. Pokud bychom chtěli najít všechna prvočísla v nějakém intervalu bez Eratosthenova síta, museli bychom ověřovat, jestli dané číslo není dělitelné beze zbytku některým menším číslem, což by bylo velmi náročné. Tento algoritmus si ale „škrtá“ všechny násobky prvočísel, a tak je podstatně rychlejší.

Máme například řadu čísel do patnácti a víme, že 2 je prvočíslo. Tím pádem všechny jeho násobky jíž prvočísly být nemohou, jelikož jsou už dělitelné dvojkou. Můžeme si je tedy vyškrtnout

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

Postup v bodech

  1. Načteme čísla v intervalu od 2 do 15

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

  1. Odebereme první číslo (2) a uložíme ho jako prvočíslo.

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

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

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

  1. Uděláme totéž pro další číslo (3)

Toto opakujeme dokud máme ještě čísla.

Vylepšení algoritmu

Algoritmus můžeme ještě vylepšit. Je totiž zbytečné procházet čísla až do hodní hranice (dále jen N). Můžeme je procházet jen do odmocniny z N. Pokud totiž budeme mít číslo zapsané jako x * y, tak x a y bude vždy <= odmocnině z N.

Ukázka v Céčku

#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ázka v Javě

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ázka 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;
        }
    }
}

 

  Aktivity (1)

Článek pro vás napsal Drahomír Hanák
Avatar
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 


Miniatura
Předchozí článek
Hornerovo schéma
Miniatura
Všechny články v sekci
Matematické algoritmy
Miniatura
Následující článek
Algoritmus náhodného čísla

 

 

Komentáře

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Pěkné, jednoduché a účinné. Profesor na matematiku nám říkal, že existují i vzorce, které vrátí všechna prvočísla a fungují do určitého rozsahu. Pokud vím, tak rovnice co pokryje všechna prvočísla je zatím mezi nejhledanějšími problémy a snad je za ni i peněžní odměna.

Odpovědět 20.8.2012 13:41
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na David Čápka
Drahomír Hanák:

Díky, Eratosthenovo síto je vhodné do 10.000.000. Pak už by se měly použít jiné metody.

 
Odpovědět 20.8.2012 13:48
Avatar
Kit
Redaktor
Avatar
Kit:

Je zbytečné počítat druhou odmocninu. Stačí jen porovnat podíl s dělitelem. Algoritmus se tím o něco málo zrychlí.

Odpovědět 20.8.2012 16:52
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 3 zpráv z 3.