Primes

A prime number is an integer greater than unity having no proper divisors.

THE FIRST K PRIMES
Prepare an array P. of K primes.

IMPLEMENTATION
Unit: internal function

Global variables: the array P.

Parameter: K - number of primes to find

Result: The first K primes are saved into the P. array

 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

PRIMALITY TEST
In exercise 3, Chapter 4.5.4, D. E. Knuth says: If 1000<=K<=1000000, then K is prime if and only if GCD(K,N)=1; N is the product of the first 168 primes. We can create a simple test function. It returns 1 or 0 depending on whether or not the K, 1000<=K<=1000000, is prime.

 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 GCD(K, N) = 1 then return 1 return 0

THE FIRST 24 MERSENNE PRIMES
Numbers of the form 2**P-1, where P is prime, are known as Mersenne numbers (according Marin Mersenne). The first 24 Mersenne primes are obtained for P equal to 2,3,5,7,...,19937. The following program only displays the number of digits in the Mersenne prime.

 /* The first 24 Mersenne primes 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

CONNECTIONS

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