Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

Sito Eratostenesa

powrót

Sito Eratostenesa jest algorytmem, który szybko znajduje wszystkie liczby pierwsze z przedziału {tex}[2..n]{/tex}. Inaczej mówiąc, przesiewa z tego zbioru liczby, w taki sposób, że zostają tylko pierwsze.

Algorytm opracował grecki matematyk, filozof, atronom - Eratostenes, który żył w latach ok. 276 r. p.n.e - ok. 194 r. p.n.e.  

Strategia przesiewania liczb jest bardzo prosta. Tworzymy tablicę {tex}n{/tex} elementową i wszystkie jej wartości ustawiamy na {tex}0{/tex}. Następnie rozpoczynamy od pierwszej liczby pierwszej (czyli {tex}2{/tex}), kierując się do komórki o tym indeksie. Komórkę {tex}2{/tex} zostawiamy niezmienioną, natomiast już każdą wielokrotność dwójki ustawiamy na {tex}1{/tex}, co będzie oznaczać, że nie jest już ona pierwszą (bo przecież dzieli się przez {tex}2{/tex}). Pokażę to na przykładzie liczb z przedziału {tex}[2..25]{/tex}

{tex}2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ 15,\ {/tex}

{tex}\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ 21,\ \not {22},\ 23,\ \not {24},\ 25{/tex}

Teraz przechodzimy do następnej komórki w tablicy, w której wartość jest równa z {tex}0{/tex}. Będzie to numer {tex}3{/tex} - ta komórka nie została oznaczona jako wielokrotność liczby {tex}2{/tex}, a więc jest ona pierwsza. Teraz każdą wielokrotność tej liczby wykreślamy ustawiając wartości tych komórek na {tex}1{/tex}:

{tex}2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ \not 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ \not{15},\ {/tex}

{tex}\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ \not {21},\ \not {22},\ 23,\ \not {24},\ 25{/tex}

W tym kroku nowo wykreślone liczby to: {tex}9,\ 15{/tex} oraz {tex}21{/tex}.

W kolejnym kroku szukamy następnej komórki, której wartość jest równa {tex}0{/tex}. Jest nią liczba {tex}5{/tex}. Powtarzamy czynność wykreślając wielokrotności tej liczby (nowo wykreślona liczba to {tex}25{/tex}). Dalej nie musimy już wykreślać, ponieważ doszliśmy do liczby {tex}\leq \sqrt {n}{/tex}. Uzasadnienie znajduje się w tym miejscu.

W ostateczności otrzymujemy:

{tex}2,\ 3,\ \not 4,\ 5,\ \not 6,\ 7,\ \not 8,\ \not 9,\ \not {10},\ 11,\ \not {12},\ 13,\ \not {14},\ \not{15},\ {/tex}

{tex}\not {16},\ 17,\ \not {18},\ 19,\ \not {20},\ \not {21},\ \not {22},\ 23,\ \not {24},\ \not{25}{/tex},

a liczby, które nie zostały wykreślone to:

{tex}2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23{/tex}

a więc same liczby pierwsze.

Zaletą takiego rozwiązania jest na pewno szybkość, natomiast poważną wadą jest ograniczenie pamięci. Musimy zadeklarować tablicę na {tex}n+1{/tex} elementów. Można to nieco obejść stosując wykreślanie bitowe, co zaprezentuję w drugim rozwiązaniu.

Prześledźmy przykład, który wypisze wszystkie liczby pierwsze z przedziału {tex}[2..n]{/tex}.

#include<iostream>
#include<cstdlib>
using namespace std;
 
void sito(bool *tab, unsigned int n)
{
  for (int i=2; i*i<=n; i++) //przeszukujemy kolejnych kandydatów na pierwsze
    {              //wystarczy sprawdzić do pierwiastka z n
                  // i<=sqrt(n) - podnosząc do kwadratu mamy
                  // i*i <= n
        if(!tab[i])        //jesli liczba jest pierwsza(ma wartosc 0)
    for (int j = i*i ; j<=n; j+=i) //to wykreslamy jej wielokrotnosci
            tab[j] = 1;      //ustawiając wartosć na 1
    }
}
 
int main()
{
  int n;
  bool *tab;
 
  cout<<"Podaj zakres górny przedziału: ";
  cin>>n;
 
  tab = new bool [n+1];
 
  for(int i=2; i<=n; i++) //zerowanie tablicy
    tab[i] = 0;
 
  sito(tab, n); //przesianie liczb
 
  cout<<"Kolejne liczby pierwsze z przedziału [2.."<<n<<"]: ";
 
  for(int i=2;i<=n;i++)
    if(!tab[i])
      cout<<i<<" ";
 
  cout<<endl;
 
  delete []tab;
 
  system("pause");
    return 0;
}
 

Drugie rozwiązanie oparte jest na odwoływaniu się do pojedynczych bitów liczby 32 bitowej. Zaletą jest to, że możemy zwiększyć maksymalny zakres tablicy w stosunku do poprzedniego rozwiązania ośmiokrotnie. Niestety program będzie wykonywał się wolniej z konieczności wykonywania obliczeń na bitach takich jak przesunięcie bitowe, koniunkcję i alternatywę bitową.

#include<iostream>
#include<cstdlib>
using namespace std;
 
void sito(unsigned int *tab, unsigned int n)
{
    for (int i=2; i*i<=n; i++) 
  {    
      if(!((tab[i>>5]>>(i&63))&1))          
      for (int j = i*i ; j<=n; j+=i)
          tab[j>>5] |= (1<<(j&63)); //ustawienie odpowiedniego bitu na 1
    }
}
 
int main()
{
    unsigned int n, *tab;
 
    cout<<"Podaj zakres górny przedziału: ";
    cin>>n;
 
    tab = new unsigned int [n/32 + 2]; //typ unsigned int składa się z 32 bitów
 
    for(int i=0; i<= n/32 + 1; i++) //zerowanie tablicy
    tab[i] = 0;
 
    sito(tab, n); //przesianie liczb
 
    cout<<"Kolejne liczby pierwsze z przedziału [2.."<<n<<"]: ";
 
    for(int i=2;i<=n;i++)            
      if(!((tab[i>>5]>>(i&63))&1))  
          cout<<i<<" ";
 
    cout<<endl;
 
    delete [] tab;
 
    system("pause");
    return 0;
}