Nem bírom meglátni ebben a prímszám kiíró kódban azt, hogy hogyan is állapítja meg egy számról, hogy melyik prím és melyik nem, hogy értelmezzem? Hogy érthetném meg a logikai működését?

Ha jól látom, 3-tól egy szám gyökéig megnézi a páratlan számokat, ha a szám eleve páratlan volt.

Ezt olvasd végig:

[link]

"if(i%2 == 0)"

A 2 prím szám, de annál nagyobb prímszámok mind páratlanok, mivel a párosak oszthatók 2-vel, tehát nem prímek.

"for(int j = 3; j < q; j += 2)"

Gondolom itt nézi meg, hogy van-e egész osztója. 3-tól indul (2 nem lehet, mert páratlan, az 1-et meg nem nézzük, mert az úgyis osztója). A ciklus a vizsgált szám gyökéig tart, vagyis a korábban számolt q-ig. Ez azért lehet, mert a gyöke * gyöke lesz a szám. Minden más kombináció úgy néz ki, hogy egy gyökénél kisebb és egy gyökénél nagyobb szám szorzata. Vagyis bárhogy írjuk fel szorzatként, az egyik szorzó biztos kisebb-egyenlő lesz a szám gyökénél. Szóval ha a gyökénél kisebb osztót nem találtunk, akkor annál nagyobbat sem fogunk, hiszen a nagyobb számot olyan számmal kellene szorozni, amit már egyszer vizsgáltunk a gyökénél kisebb tartományban.

Ha mondjuk a 29-ről el akarod dönteni, hogy prímszám-e, akkor meg kell nézned, hogy oszható-e maradék nélkül 2-vel, 3-mal, 4-gyel, 5-tel, stb., egészen 28-ig.

Nagy számok esetén ez elég sok idő lehet, még programmal is. Az egyik egyszerűsítés, ha csak a szám feléig nézzük, mivel annál nagyobb számmal úgysem oszható. Tehát a 29/20 például tuti, hogy nem lesz egész szám.

Mivel a prímszámok csak 1-gyel és önmagukkal oszthatók maradék nélkül, a 2-vel való oszthatóság is kizáró tényező. (Kivéve a 2-t.) Tehát 2 fölött eleve csak a páratlan számok lehetnek prímek, vagyis csak 3-tól kell nézni a feléig.

További egyszerűsítés, amikor csak a gyökéig nézzük, ami a felénél is kisebb. Tehát egy szám vizsgálatakor csak 3-tól a szám gyökéig kell végignézni a számokat, hogy oszható-e a vizsgált számmal.

A gyökös dolog:

Nézzük pl. a 16-ot. Ez így írható fel:

1*16

2*8

4*4

8*2

16*1

Látszik, hogy amikor elérünk a gyök*gyök szorzatig (4*4), akkor már csak ismétlődik a lista, csak megfordítva. Tehát elég odáig vizsgálni, mert azután már semmi újat nem fogunk találni.

A progi részlet:

Valószínűleg az egész egy nagyobb ciklus magja. Gondolom a külső ciklusban i fut végig a vizsgálandó számokon, hogy i prím-e.

A count nem igazán értem, talán azt számolja, hány számot vizsgált meg eddig. Bár nem értem, miért pont a páros ágba lett téve az inkerementálás... működik, csak fura.

Az if vizsgálja, hogy páros-e a szám, amit épp nézünk. Ha páros, akkor nem csinál semmit (csak számol, de ennyi). Ha viszont páratlan, akkor elkezd egy újabb ciklust.

Ez a for ciklus fog végigszaladni a számokon 3-tól az i gyökéig, ráadásul csak a páratlan számokon (j += 2). Tehát 3,5,7,9, stb. Azért a páratlanokon, mert így helyből kizárja a 2-vel osztható számokat. (Ezért elég 3-tól indítani a ciklust.)

:)