Eratoszthenész szitája

A prímszámok előállításának ma is használt módszere Eratoszthenész görög matematikustól származik. Az elnevezés utal az eljárás lényegére, mivel az 1-től n-ig felírt egész számok közül “kiszitáljuk” az összetett számokat. Amely számok fennmaradnak a “szitán” (az 1 kivételével) azok a prímek.

Az eljárás:

1. Írjuk fel a számokat 1-től n-ig, (itt például 100-ig) egyesével.
2. Keressük meg az első olyan 1-től nagyobbat, amelyik még nincs sem kihúzva, sem megjelölve. Elsőként ez a 2.
3. Ezután húzzuk ki ennek többszöröseit, de őt pedig jelöljük meg.
4. Ismételd meg a második lépéstől újra az eljárást. Természetesen egy összetett szám többször is kihúzásra kerülhet.
5. Az algoritmus akkor álljon le, ha a második lépésnél talált szám négyzete már nagyobb, mint n.

1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 100

 

Print Friendly, PDF & Email

Comments are closed, but trackbacks and pingbacks are open.