Eratoszthenész szitája
prímszámok keresésének egyik algoritmusa
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.
![Eratoszthenész szitája](http://upload.wikimedia.org/wikipedia/commons/1/1f/Animation_Sieve_of_Eratosth_HU.gif)
Az algoritmus
szerkesztés- 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
szerkesztésAz 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
szerkesztés#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#
szerkesztés 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++
szerkesztésOptimá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]
szerkesztésprogram 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
szerkesztés#!/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
szerkesztéspublic 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
szerkesztés- ↑ Simkó Lajos: Simkó Lajos gyakori kérdések, válaszok - Eratoszthenész szitája. (Hozzáférés: 2016. február 26.)
Források
szerkesztés- Κόσκινον Ἐρατοσθένους 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
szerkesztés- Animált eratoszthenészi szita 1000-ig
- Eratoszthenész szitája magyarázat, animáció
- Java Script-animáció Archiválva 2001. március 1-i dátummal a Wayback Machine-ben