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. Prímszámok 100 in english. Length; i ++)
if ( nums [ i])
Console. Write ( $"{i} ");}}
Console. ReadLine ();
Programkód C++-ban [ szerkesztés]
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
Programkód Pythonban [ 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) Jegyzetek [ szerkesztés] 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 Java Script animáció
for ( int i = 2; i <= M; ++ i) tomb [ i] = true; //2-től indítjuk a for-t, alapból mindent igazra állítunk.
Például 2 10 =1024. Ha az 1024-et elosztjuk 10+1=11-el, akkor a maradék 1 lesz. A 11 pedig tényleg prím. Ha viszont a 2 11 =2048-al tesszük ugyanezt, azaz 2048-at elosztjuk 11+1=12-vel, akkor 8-at kapunk maradékul, nem 1-et, de hát a 12 nem is prím. Ezek egyszerű példák, de az a p-1 -nek p-vel való osztási maradékának a meghatározása viszonylag hatékony, ezért ez egy elég jó eljárás egy szám összetettségének megállapítására.
A prímszámok fogalmát valószínűleg már az egyiptomiak és a mezopotámiai népek is ismerték. Első, tervszerű tanulmányozói a püthagoreusok voltak, de a prímszámokra először Eukleidésznél találunk pontos meghatározást. Mivel a prímszámok a természetes számok, illetve az egész számok "atomjai", mindig nagyon foglalkoztatták a matematikusokat. A prímszámokkal kapcsolatos legfontosabb kérdések: • Prímszámok előállítása. • Prímszámok elhelyezkedése, eloszlása. • Prímszámok fajtái. • Minél nagyobb prímszámot találni. • Hogyan lehet egy számról megállapítani, hogy prím-e? Prímszámok előállításáról: Mivel az eratoszthenészi szita nagy számok esetén meglehetősen fáradságos (főleg, amikor még számítógépek sem álltak rendelkezésre), sok matematikus próbált a prímszámok előállítására formulát találni, de ezek a kísérletek nem jártak sikerrel. Érdekes megemlíteni Euler képletét: p(n)=n 2 +n+41. Ez a képlet prímszámokat ad n=1-től n=39-ig, de könnyű belátni, hogy n=40 illetve n=41 esetén a kapott szám összetett szám lesz.
Legyen a=3, b=5, így (3;5)=1, tehát 3⋅n+5 alakú számok között végtelen sok prímszám van. (n=1 esetén az érték 8 nem prím, n=2 esetén 11, ez prím, stb. ) 2. Nagyon sok prímszám n 2 +1 alakú, ahol n pozitív egész. Nyitott kérdés, hogy az ilyen típusú prímszámokból végtelen sok van-e? Megjegyzés: Persze, ez a formula sem mindig prímszámot ad. Például n=1 esetén 2, n=2 esetén 5 is prím, de n=3 esetén 10 már nem prím. 3. 2 n +1 alakú Fermat-féle prím, ahol n kettő hatvány, azaz n=2 k, ahol k nem-negatív egész. Például ez a kifejezés k=0, 1, 2, 3, 4 esetén prímszámot ad, ezek 20+1=3, 22+1=5, 24+1=17, 28+1=257, 216+1=65537, de k=5 esetén a 232+1=4 294 967 296+1=4 294 967 297 nem prím, mivel 4 294 967 297=641*6 700 417. Ezt Euler mutatta ki. Kétséges, hogy k>5 esetén a kapott számok prímek-e. Persze minden Fermat féle prím egyben n 2 +1 alakú is. Érdekes geometria kapcsolat van a Fermat-féle prímek és a szabályos sokszögek szerkeszthetősége között. Gauss bebizonyította, hogy az n oldalú prímszám oldalszámú szabályos sokszögek közül csak azok szerkeszthetők, amelyeknél az oldalak száma Fermat-féle prím.