Vydělávej až 160.000 Kč měsíčně! Akreditované rekvalifikační kurzy s garancí práce od 0 Kč. Více informací.
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í.

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í:
11 hlasů
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.
Aktivity