Tananyag választó:
Esettanulmányok
Jegyzet szerkesztése:
Végrehajtási idő csökkentése I
Eszköztár:

A feladat általános, nem hatékony megoldása

A prímszámok definíciója alapján írható az alábbi algoritmus, amely eldönti, hogy adott k természetes szám prím vagy nem.
Függvény Prím(K: Egész): logikai;
Változó I: Egész;
I:=2;
Ciklus míg (I<K) ÉS (I nem osztja K-t)
I:=I+1;
CiklusVége;
Prím:=(I<K);
FüggvényVége;
A következő algoritmus azt vizsgálja, hogy az adott tartományban találhatóak-e ilyen számpárok.
Be: N;
Ciklus I:=2..N-2
Ha Prím(I) ÉS Prím(I+2) akkor Ki: I, I+2;
CiklusVége;

Végrehajtási idő csökkentése, 1.lépés

A prímszámok vizsgálata során célszerű figyelembe venni, definíción kívül a prímek tulajdonságait és oszthatósággal kapcsolatos ismereteket is.
A prím-vizsgálat lényegében annak eldöntése, hogy az adott számnak létezik-e valódi osztója. Mivel egyetlen természetes számnak sem lehet a négyzetgyökénél nagyobb valódi osztója, ezért a lehetséges osztókat elegendő csak addig sorra venni.
Függvény Prím(K: Egész): logikai;
Változó I: Egész;
I:=2;
Ciklus míg (I≤Gyök(K)) ÉS (I nem osztja K-t)
I:=I+1;
CiklusVége;
Prím:=(I<K);
FüggvényVége;
Mivel a gyökvonás időigényesebb művelet a szorzásnál, az I≤Gyök(K) kifejezés helyett célszerű a (I*I)≤K kifejezést írni.

Végrehajtási idő csökkentése, 2.lépés

Könnyen belátható, hogy iker-prímek csak páratlan számok lehetnek (egyetlen páros prím van, a 2, de annak nincs iker-prím párja, mert a 2+2 összetett szám). Mindez azt jelenti, elegendő a keresést a 2-nél nagyobb páratlan egészek körében elvégezni.
Be: N;
I:=3;
Ciklus míg I≤(N-2)
Ha Prím(I) ÉS Prím(I+2) akkor Ki: I, I+2;
I:=I+2;
CiklusVége;

Végrehajtási idő csökkentése, 3.lépés

Be: N;
I:=3;
Ciklus míg I≤(N-2)
Ha Prím(I) akkor
Ha Prím(I+2) akkor
Ki: I, I+2;
I:=I+2;
különben
I:=I+4;
HaVége;
Különben
I:=I+2;
HaVége;
CiklusVége;

Végrehajtási idő csökkentése, 4.lépés

Ha egy sorozat elemeit úgy határozzuk meg, hogy az növekvő sorrendben csak egy adott n-nél nem nagyobb páratlan prímeket tartalmazza, akkor elegendő csak a szomszédos elemek különbségét vizsgálni. Ha az 2, akkor a két vizsgált elem ikerprím.