Sito Eratostenesa

Animacja sita eratostanesa

Sito Eratostenesa - algorytm wyznaczania liczb pierwszych z zadanego przedziału $[2,n]\;$.

Algorytm

Ze zbioru liczb naturalnych z przedziału $[2,n]\;$, tj. $\{2, 3, 4, \dots, n\}$, wybieramy najmniejszą, czyli 2, i wykreślamy wszystkie jej wielokrotności większe od niej samej, to jest $4, 6, 8, \dots$.

	2	3	-4-	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	-44-	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Z pozostałych liczb wybieramy najmniejszą niewykreśloną liczbę (3) i usuwamy wszystkie jej wielokrotności większe od niej samej: $6, 9, 12, \dots$, przy czym nie przejmujemy się tym, że niektóre liczby (na przykład 6 czy 12) będą skreślane więcej niż raz.

	2	3	-4-	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	-44-	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Według tej samej procedury postępujemy dla liczby 5.

	2	3	-4-	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	-44-	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Następnie dla 7, 11, 13; aż do sprawdzenia wszystkich niewykreślonych wcześniej liczb.

	2	3	-4-	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	-44-	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Wykreślanie powtarzamy do momentu, gdy liczba $i\;$, której wielokrotność wykreślamy, będzie większa niż $\sqrt{n}$.

Dla danej liczby $n\;$ wszystkie niewykreślone liczby mniejsze, bądź równe $n\;$ są liczbami pierwszymi.

	2	3	-4-	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	-44-	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60

Implementacja

C++

#include <iostream>
 
using namespace std;
 
const int n = 100;
 
bool numbersTable[n + 1]; // tablica o indeksach od 0 do 100 | wszystkie false (czyli: 0);
 
int main()
{
    for (int i = 2; i*i <= n; i++ ) // przeszukuj liczby od 2 do sqrt(n), 0 i 1 nie są liczbami pierwszymi
    {
        if (numbersTable[i] == true) // jeżeli dana liczb jest już wykreślona
            continue; // to przejdź do kolejnej
        for (int j = 2 * i ; j <= n; j += i) // przejdź od liczby 2 * i do n przesuwając się o i
            numbersTable[j] = true; // i każdą z nich usuwaj ze zbioru
    }
 
    cout << "Liczby pierwsze z przedziału od 2 do " << n << ":" << endl;
 
    for (int i = 2; i <= n; i++) // przeszukaj liczby od 2 do n
        if (numbersTable[i] == false) // jeśli liczba nie została usunięta ze zbioru
            cout << i << endl; // to ją wypisz
    return 0;
}

C#

namespace ConsoleApplication
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = 0;
            Console.Write("Podaj liczbe: ");
            n = Convert.ToInt32(Console.ReadLine());
            bool[] tab = new bool[n+1];
            for (int i = 2; i * i <= n; i++)
            {
                if (tab[i] == true)
                {
                    continue;
                }
                for (int j = 2 * i; j <= n; j += i)
                {
                    tab[j] = true;
                }
            }
            Console.WriteLine("Liczby pierwsze z zakresu [0," + n + "]: ");
            for (int i = 2; i <= n; i++)
            {
                if (tab[i] == false)
                {
                    Console.Write(i + " ");
                }
            }
            Console.ReadKey();
        }
    }
}

Pascal

program sito eratostenesa
var
tablica : array[2..100] of boolean;
i, b, c : integer;
n : int64;
 
begin
  n := 100;
  for i := 2 to n do tablica[i] := false;
 
  i := 1;
  repeat
    i := i + 1;
    b := 2 * i;
      repeat
        tablica[b] := true;
        b := b + i;
      until (b > n);
  until i > sqrt(n);
  for i := 2 to n do
  begin
    if (not tablica[i]) then
    write(i, ' ');
  end;
end.

Java

public class Main 
{
    public static void main(String[] args)
    {
        int n = 100;
        boolean[] numbersTable = new boolean[n+1];
        for(int i = 2; i*i <= n; i++)
        {
            if (numbersTable[i] == true)
                continue;
            for (int j = 2 * i ; j <= n; j += i)
                numbersTable[j] = true;
 
        }
        System.out.println("Liczby pierwsze z przedziału od 2 do " + n + ":");
        for (int i = 2; i <= n; i++)
            if (numbersTable[i] == false)
                System.out.println(i);
 
    }
 
}

Asembler

segment .data 
limit   dd      2000000
segment .text
        global  _start
_start: 
        push    ebp
        mov     ebp,esp
 
        mov     ecx,[limit]
L1:
        push    ecx
        dec     ecx
        cmp     ecx,1
        jne     L1
 
        mov     ebx,4
L2:
        mov     edi,esp
        pop     ecx     
        cmp     ecx,0
        je      notPrime
 
        mov     eax,ecx
        call    _printEAXdecimal
 
        mov     eax,ecx
        xor     ecx,ecx
        mul     ebx
L3:
        mov     [edi],ecx
        add     edi,eax
        cmp     edi,ebp
        jg      notPrime
        jmp     L3
 
notPrime:
        cmp     ebp,esp
        jne     L2
 
        pop     ebp
 
        mov     eax,1   ; exiting
        mov     ebx,5
        int     0x80

MATLAB

function liczby_pierwsze=esito2(wektor)
%Sito Eratostenesa
zakres=2:floor(sqrt(max(wektor)));
liczby_pierwsze=wektor;
for i=1:length(zakres)
    liczby_pierwsze=liczby_pierwsze(mod(liczby_pierwsze,zakres(i))~=0 & liczby_pierwsze~=zakres(i));
end
end

Zobacz też

• sito Atkina
• Eratostenes

Linki zewnętrzne

• Animacja sita Eratostenesa
• implemetacja sita Eratostenesa w języku java