jobbra|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.

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ódok C #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; int i,j; nemnegativ_egesz_szamok=0; nemnegativ_egesz_szamok=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; }

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

nums = 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();

C++ 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 << "Prímszámok " << M << "-ig:\n"; //A fájl bevezető szövege bool tomb[M + 1]; //logikai tömböt hozunk létre tomb = tomb = 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

Pascal 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 := 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.

Python #!/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)

Java 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);

Jegyzetek

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 Eratoszthenész szitája magyarázat, animáció Java Script-animáció

Kategória:Algoritmusok Kategória:Szitaelmélet