Azt ugy is tudjuk, hogy 2 kivetelevel minden masodik szam NEM prim, tok felesleges oket ellenorizni. Leptessed kettesevel a ciklust es ugrald at a paros szamokat."
Gyokvonas sem kell igazan, az is kikoszobolheto, eltarolva egy szamot es negyzetet, a szamig ellenorzod, a negyzetenel kisebb gyanisitottakra, amint nagyobb szamokat kell vizsgalni a szamot noveled egyel, es ujra szamolod a negyzetet. Ez egy hasonlitast eremenyez, nemely elysetben egy inc + szorzast is, ami meg mindig kevesebb mint egy gyokvonas ido igenye.
Valamint eleg csak a mar megtalt primmekkel probalkozni mod ra.
Ha csak 1000000 kellenek akkor szita modszert is lehet hasznalni.
Nagyabol:
0. 10000000 elemu bitvektor kezdo ertek true.
,
p=2
1. minden pedik megjelol falsnak
2. a legkisebb meg nem hasznalt true val jelzett index el legyen egyenlo p