Gyakorlati alapok
100 tagú prímszám zenekar
Az előző fejezet algoritmusát felhasználva most stílusosan állapítsuk meg az első 100 prímszámot!
Kis matematikai visszaemlékeztető:
Prímnek nevezzük azokat a természetes számokat, amelyeknek a természetes számok között kizárólag 2 osztójuk van: egyik önmaguk, a másik az 1. Tehát ezek a számok magukon és az 1-en kívül nem oszthatók más számmal.
Adott tartományú prímszámkeresést még mindig nem ússzuk meg iterálás nélkül (for ciklus), hiszen végig kell próbálnunk az összes lehetséges oszthatóságot a keresett számon. A keresett szám itt a külső főciklus léptetője lesz (int i). Mivel 0 és 1 nem prímszám, a léptetést 2-től indítjuk (int i = 2). Most is deklaráltunk egy klasszikus flag-et, azaz 2 állású állapotváltozót (boolean prim = true;), ennek értékét csakis a prímszám sikertelen megtalálásakor változtatjuk meg false értékre.
Egyéb más feltételre nincs szükségünk, indulhat tehát a prímáskeresés a belső for ciklusban. Az iterálás 2-nél kezdődik (int j = 2;) és a keresett szám négyzetgyökéig tart (Math.sqrt(i)), mert a keresett szám (i) más számokkal való oszthatósága eddig a matematikai pontig kiderül. Ezen határig az algoritmus azt nézi meg, hogy i szám j változóval osztott maradéka 0-e (if (i % j == 0)). Ha igen, a keresett szám nem prím, másként az.
public class Main {
public static void main(String[] args) {
boolean prim = true;
for(int i = 2; i <= 100; i++){
prim = true;
for (int j = 2; j <= Math.sqrt(i); j++){
if (i % j == 0){
prim = false;
break;
}
}
if(prim == 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
No de ácsi Laci bácsi, ez nem 100 db prímszám, hanem csak 25!
Pontosítsunk: ott tévesztettünk, hogy feltételként az első 100 számból választottuk ki a prímszámokat, ám ez a feltétel nem ugyanaz, mint az eredeti.
Ahhoz, hogy megtaláljuk az első 100 db prímszámot, be kell vetnünk egy számlálót, amely a prímszámok mennyiségét számlálja (int szamlalo = 0;) olyan módon, hogy prímszám találása esetén értékét 1-gyel növeljük (szamlalo++). Ha eléri a 100 értéket, valamilyen módon leállítjuk a főciklust. Itt azonban egy újabb problémába ütközünk: nem ismerjük a külső főciklus felső határát (i <= ?), azaz nem tudjuk, hogy hány számot kell átvizsgálnunk 100 db prímszám megtalálásához.
Többféle megoldásunk is van a tenyerestalpastól egészen az optimálisig. Nézzük meg először az előbbit!
Mivel 100 db átvizsgálása után 25 db prímszámunk keletkezett, kézenfekvő, hogy 100 db prímszámhoz nagyjából 400-500 számot szükséges megvizsgálnunk; ekkor még számlálót sem használunk fel. Ez persze olyan intuitív hivatkozás, amelynek semmiféle matematikai alapja sincs, bár a "másik oldal" érvelése szintén hamis lehet, miszerint a prímszámok növekedése kaotikus a számsoron. Mindenesetre az a legvalószínűbb, hogy a prímszámok azonos módon vagy éppen kissé csökkenő sűrűséggel követik egymást. Az alábbi futtatható Java-kódban tehát csak a felső határt változtattuk meg (i <= 400;):
public class Main {
public static void main(String[] args) {
boolean prim = true;
for(int i = 2; i <= 400; i++){
prim = true;
for (int j = 2; j <= Math.sqrt(i); j++){
if (i % j == 0){
prim = false;
break;
}
}
if(prim == 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
A fenti intuitív megjegyzés bár helyes volt, hiszen 400 elemű számsorból 78 db prímszámot szűrtünk ki, amely a csökkenő sűrűséget bizonyítja, ám a megoldás mégsem elegáns, sőt elnagyolt és pontatlan. Valójában a for ciklus sem az optimális motor a teszteléshez; nála sokkal jobb megoldásnak ígérkezik a hátultesztelő do - while ciklus, mert nekünk csakis addig kell a ciklust működtetni, amíg a számláló eléri a 100 értéket (while(szamlalo != 100)):
public class Main {
public static void main(String[] args) {
boolean prim = true;
int szamlalo = 0;
int i = 1;
do{
i++;
prim = true;
for (int j =
2; j <= Math.sqrt(i); j++){
if (i % j == 0){
prim = false;
break;
}
}
if(prim ==
true){
System.out.print(i + " ");
szamlalo++;
}
}while(szamlalo != 100);
}
}
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 503 509 521 523 541
Pénzes László