PRVOČÍSLA

---

Prvočíslo je celé číslo větší než 1, které nemá jiného dělitele než jedničku a sebe sama.

PRVNÍCH K PRVOČÍSEL

Pole P.1,...,P.M máme naplnit prvními K prvočísly.

IMPLEMENTACE

Jednotka: vnitřní funkce
 
Globální proměnné: pole P.
 
Parametr: K - počet požadovaných prvočísel
 
Výsledek: V poli P. je uloženo prvních K prvočísel

 

PRIMES: procedure expose P. parse arg K P.1 = 2; N = 3 do J = 2 to K   P.J = N   do forever     N = N + 2     do L = 2 until R = 0       Q = N % P.L; R = N // P.L       if Q <= P.L & R <> 0 then iterate J     end   end end return

 

TEST NA PRVOČÍSLA

Ve cvičení třetím, v kapitole 4.5.4, D. E. Knuth píše: Je-li 1000<=K<=1000000, pak K je prvočíslo tehdy a jen tehdy, když NSD(K,N)=1; N je tu součinem prvních 168 prvočísel. Můžeme napsat jednoduchou funkci, vracející hodnotu 1 nebo 0 v závislosti na tom, je-li K, 1000<=K<=1000000, prvočíslo nebo není.

 

PRIMALITY_TEST: procedure parse arg K call PRIMES(168) numeric digits 416 N = 1 do J = 1 to 168; N = N * P.J; end if NSD(K, N) = 1 then return 1; else return 0

 

PRVNÍCH 24 MERSENNEHO PRVOČÍSEL

Někdy se nám může hodit nějaké opravdu velké prvočíslo. Čísla 2**P-1, kde P je prvočíslo, se nazývají Mersenneho čísla, podle Marina Mersenneho. Prvních 24 Mersenneho prvočísel získáme pro P rovno 2,3,5,7,...,19937. Následující program zobrazí jen délku, tj. počet číslic těchto prvočísel.

 

/* Prvních 24 Mersenneho prvočísel 2 3 5 7 13 17 19 31 61 89 107 127 521 607 1279 2203 2281 3217 4253 4423 9689 9941 11213 19937 */ numeric digits 6002 do I = 2 while SOURCELINE(I) <> "*/"   Row = SOURCELINE(I)   do while Row <> ""     parse var Row Num Row     P = 2 ** Num - 1; say "P =" LENGTH(P)   end end

 

SOUVISLOSTI

Euklidův algoritmus pro výpočet NSD (a NSN)

Literatura

Knuth D. E. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming

Addison-Wesley, 1973

---