Black Friday je tu! Využij jedinečnou příležitost a získej až 80 % znalostí navíc zdarma! Více zde
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
BF extended 2022

Lekce 14 - Eratosthenovo síto

V minulé lekci, Hornerovo schéma, jsme si ukázali Hornerovo schéma. Už víme, že to je algoritmus pro efektivní výpočet hodnoty mnohočlenu příp. jeho derivace. Je užitečný mj. i pro převod čísla do desítkové soustavy.

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

  • #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;
    }
  • 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);
        }
    
    }
  • 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;
            }
        }
    }

 

Předchozí článek
Hornerovo schéma
Všechny články v sekci
Matematické algoritmy
Článek pro vás napsal Drahomír Hanák
Avatar
Uživatelské hodnocení:
3 hlasů
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.
Aktivity

 

 

Komentáře

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:20.8.2012 13:41

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
One of the most common causes of failure is the habit of quitting when one is overtaken by temporary defeat.
Avatar
Odpovídá na David Čápka
Drahomír Hanák:20.8.2012 13:48

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
Tvůrce
Avatar
Kit:20.8.2012 16:52

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ů.
Avatar
BluPri
Člen
Avatar
Odpovídá na Drahomír Hanák
BluPri:18.4.2017 11:51

Jaké metody to jsou? :-)

 
Odpovědět
18.4.2017 11:51
Avatar
Šimon Rataj
Člen
Avatar
Šimon Rataj:14.11.2017 14:33

Udělal jsem to v PHP asi před rokem.

function prvocisla($int) {
    for($i = 0; $i<=$int; $i++) {
      $r[0] = 1;
      if($i>0)
        $r[$i-1] = $i;
      unset($r[0]);
    };
    foreach($r as $k => $v) {
      for($i = $v; $i<$int; $i++) {
        if(isset($r[$i]) && $r[$i]%$v==0)
          unset($r[$i]);
      };
    };
    return $r;
  };

$int je maximum
Zde to funguje.

Editováno 14.11.2017 14:35
 
Odpovědět
14.11.2017 14:33
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 5 zpráv z 5.