Gyakorlati alapok
Eratoszthenész szitája
Az előző fejezetekből...
...mindenféle módszerrel és határok között kinyertük a számok közül a prímszámokat. De a sokféle prímszámkereső algoritmus közül talán az ógörög matematikus, Eratoszthenész (Kr. e. 276.-197 k.) szitája volt a legelső.
Módszere rendkívül egyszerű és éppen ezért zseniális:
-
vesszük a természetes számok sorozatát (1, 2, 3, 4, ...) tetszőleges h határig, amelyben tehát 0 < n < h;
-
a sorozat 1-gyel kezdődik, de mivel az nem prímszám, a következő szám a 2,
-
húzzuk ki 2 többszöröseit, mivel azok így nem prímszámok, de őt magát jelöljük meg,
-
a következő, nem bejelölt számtól ismételjük meg az eljárást,
-
természetesen egy szám többször is kihúzásra kerülhet, de ha már egyszer kihúzott, nem kell többé foglalkozni vele,
-
az algoritmus akkor álljon le, ha a 3. lépésnél talált szám négyzete már nagyobb, mint n.
Az algoritmust azért nevezzük szitának, mert az eljárást kézzel végrehajtva, az összetett számok látványos, színezett kihúzása mintegy "kiszitálja" a prímszámokat a természetes számok közül.
Nem tagadom, hogy a kód nem saját találmány, hanem C nyelvből írtam át. Ez nem volt nehéz, hiszen a Java egyik közvetlen őséről beszélünk. Ilyesfajta eljárás egyébként része a mindennapi programozói tevékenységnek, hiszen ez a szakma is tele van eredendően lusta emberekkel.
Nézzük meg a futtatható Java-kódot:
public class Main {
public static void main(String[] args) {
int hatar = 500;
boolean[] tomb = new boolean[hatar+1];
int i, j;
tomb[0] = false;
tomb[1] = false;
for(i = 2; i <= hatar; i++){
tomb[i] = true;
}
for(i = 2; i * i <= hatar; i++){
if(tomb[i] == true){
for(j = i *
i; j <= hatar; j += i){
tomb[j] = false;
}
}
}
for(i = 0; i <= hatar; i++){
if(tomb[i] == true){
System.out.print(i + " ");
}
}
}
}
Végeredmény:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
Pénzes László