Milyen elven lehet a legelegánsabban listázni egy adott tartományba eső prímszámokat?

Ez a tartomány nagyságától és helyzetétől is függ. Illetve attól is függ, hogy papíron, számológéppel, vagy számítógéppel akarsz-e számolni. Ha x kellően kicsi, valamint y sem túl nagy akkor a hagyományos módszert érdemes használni:

A a szám esetén elkezded 3-tól gyök(a)-ig kettesével venni a számokat, és mindegyiknél megnézni, hogy nem ad-e 0-t maradéknak. Ha igen, akkor azzal a számmal osztható, tehát nem prím.

Ezt lehet úgy is optimalizálni, hogy külön vezeted egy tömbben az eddig megtalált prím számokat, és csak ezekkel végzed el az osztási próbált. Ez gyorsabb, de több memóriát fog enni egy program esetében. Papíron célszerű is ezt használni.

Aztán ott van ez is: [link]

Ha viszont a 10^523 -tól kell az első 100 prímszámot kiírni, akkor nem ez a megfelelő módszer. Itt érdemesebb lehet a kis Fermat-tételt használni: [link]