Eratoszthenész szitája

Eratoszthenész szitája

Eratoszthenész szitája vagy eratoszthenészi szita a neves ókori görög matematikus, Eratoszthenész módszere, melynek segítségével egyszerű kizárásos algoritmussal megállapíthatjuk, hogy melyek a prímszámok – papíron például a legkönnyebben 1 és 100 között.

Az algoritmus

1. Írjuk fel a számokat egymás alá 2-től ameddig a prímtesztet elvégezni kívánjuk. Ez lesz az A lista. (Az animáció bal oldalán.)

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

2. Kezdjünk egy B listát 2-vel, az első prímszámmal. (Az animáció jobb oldalán.)

3. Húzzuk le 2-t és az összes többszörösét az A listáról.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

4. Az első át nem húzott szám az A listán a következő prím. Írjuk fel a B listára.

5. Húzzuk át az így megtalált következő prímet és az összes többszörösét.

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

6. Ismételjük a 3–5. lépéseket, amíg az A listán nincs minden szám áthúzva.

A pszeudokód

Az algoritmus pszeudokódja:

 // legfeljebb ekkora számig megyünk el
 utolso ← 100

 // abból indulunk ki, hogy minden szám prímszám
 ez_prim(i) ← igaz, i ∈ [2, utolso]

 for n in [2, √utolso]:
     if ez_prim(n):
         // minden prím többszörösét kihagyjuk,
         // a négyzetétől kezdve
         ez_prim(i) ← hamis, i ∈ {n², n²+n, n²+2n, …, utolso}

 for n in [2, utolso]:
     if ez_prim(n): nyomtat n

Programkód C-ben

#include <stdio.h>

int main(){
    //0 és 1 kivételével (mivel ezek nem prímek) az összes számot prímnek feltételezzük (1)
    int nemnegativ_egesz_szamok[1001];
    int i,j;
    nemnegativ_egesz_szamok[0]=0;
    nemnegativ_egesz_szamok[1]=0;
    for(i=2;i<=1000;i++){
        nemnegativ_egesz_szamok[i]=1;
    }
    //Végigmegy a számokon 2-től a felső korlátig, és ha az prím, akkor a többszöröseit hamissá (0) teszi
    for(i=2;i*i<=1000;i++){
        if(nemnegativ_egesz_szamok[i]==1){
            for(j=i*i;j<=1000;j+=i){
                nemnegativ_egesz_szamok[j]=0;
            }
        }
    }
    //Kiírjuk a képernyőre a prímszámokat
    for(i=0;i<=1000;i++){
        if(nemnegativ_egesz_szamok[i]==1){
            printf("%d ",i);
        }
    }
    return 0;
}

Programkód C#-ban

            Console.WriteLine("Kérem N értékét: ");
            string s = Console.ReadLine();
            int n = Convert.ToInt32(s);
            bool[] nums = new bool[n];

            nums[0] = false;

            for (int i = 1; i < nums.Length; i++)
            {
                nums[i] = true;
            }

            int p = 2;

            while (Math.Pow(p, 2) < n)
            {
                if (nums[p])
                {
                    int j = (int) Math.Pow(p, 2);

                    while (j < n)
                    {
                        nums[j] = false;
                        j = j + p;
                    }
                }

                p++;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (nums[i])
                {
                    Console.Write($"{i} ");
                }
            }

            Console.ReadLine();

Programkód C++-ban

Optimális C++-kód, fájlba írással

//Az első M (itt 50) szám közül válogassuk ki a prímeket, fájlba írja az eredményt - Eratoszthenész Szitája
#include <iostream>
#include <fstream>
#include <string>

using namespace std;
int main()
{
	ofstream fout;
	string nev;
	cout << "Nev: "; cin >> nev; //fájlnév bekérése
	fout.open(nev.c_str());      //fájl létrehozása

	const int M = 50; //Meddig vizsgáljuk a számokat
	fout << "A(z) " << M << "-nel nem nagyobb primszamok:\n"; //A fájl bevezető szövege
	bool tomb[M + 1]; //logikai tömböt hozunk létre
	tomb[0] = tomb[1] = false; // a 0-át és az 1-et alapból hamisnak vesszük, hiszen nem prímek.
	for (int i = 2; i <= M; ++i) tomb[i] = true; //2-től indítjuk a for-t, alapból mindent igazra állítunk.
	for (int i = 2; i*i <= M; i++) {
		if (tomb[i]) {
			// prímet találtunk, a többszöröseit kiszitáljuk
			for (int j = i*i; j <= M; j += i) tomb[j] = false;
		}
	}

	for (int i = 0; i <= M; ++i) {
		if (tomb[i]) { //megnézzük hogy igaz-e
			fout << i << " "; // kiírja a fájlba a számokat, szóközzel elválasztva
		}
	}
}

Programkód Pascalban

program Eratoszthenesz_szitaja;

{$APPTYPE CONSOLE}

uses SysUtils;

var n, i, j, p:longint;
  a: array of boolean;
begin
  Write('Kérem N értékét: ');
  ReadLn(n);
  SetLength(a, n + 1);
  a[1] := False;
  for i := 2 to n do a[i] := True;
  p := 2;
  while p * p <= n do
  begin
    if a[p] then
    begin
      j := p * p;
      while j <= n do
      begin
        a[j] := False;
        Inc(j, p);
      end;
    end;
    Inc(p);
  end;
  for i := 1 to n do if a[i] then Write(i, ' ');
  SetLength(a, 0);
  ReadLn;
end.

Programkód Pythonban

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from math import sqrt

n = 1000
lst = [True]*n                      # létrehozunk egy listát, ebben a példában 1000 elemmel
for i in range(2,int(sqrt(n))+1):     # A lista bejárása a 2 indexértéktől kezdve a korlát gyökéig
    if (lst[i]):                      # Ha a lista i-edik eleme hamis, akkor a többszörösei egy előző ciklusban már hamis értéket kaptak, így kihagyható a következő ciklus.
        for j in range(i*i, n, i):      # a listának azon elemeihez, melyek indexe az i-nek többszörösei, hamis értéket rendelünk
            lst[j] = False
for i in range(2,n):                # Kiíratjuk azoknak az elemeknek az indexét, melyek értéke igaz maradt
    if lst[i]:
        print(i)

Programkód Javában

public static void sieve(int limit) {
  var lst = new boolean[limit];
  for (int i = 2; i < limit; i++) {
    if (!lst[i]) {
      for (int j = i + i; j < limit; j += i) {
        lst[j] = true;
      }
    }
  }
  for (int i = 1; i < limit; i++) {
    if (!lst[i]) {
      System.out.println(i);
    }
  }
}

Források

• Κόσκινον Ἐρατοσθένους or The Sieve of Eratosthenes (Being an Account of His Method of Finding All the Prime Numbers), Rev. Samuel Horsley, F. R. S. = Philosophical Transactions (1683–1775), 62(1772), 327–347.

További információk

• Animált eratoszthenészi szita 1000-ig
• Java Script-animáció Archiválva 2001. március 1-i dátummal a Wayback Machine-ben