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 | 5 | 7 | 9 | 11 | 13 | 15 | 17 | 19 |
- 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 | 5 | 7 | 11 | 13 | 17 | 19 |
- 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[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; }
C#
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();
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 << "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 } } }
Pascal[1]
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.
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
- ↑ Simkó Lajos: Simkó Lajos gyakori kérdések, válaszok - Eratoszthenész szitája. (Hozzáférés: 2016. február 26.)
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
- Informatikai portál
- Matematikaportál