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

Literatura
Knuth D. E. Seminumerical Algorithms, vol. 2 of The Art of Computer Programming
Addison-Wesley, 1973


obálka obsah index hlavní

změněno 12. dubna 2018
Copyright © 2000-2018 Vladimír Zábrodský, RNDr.

mail