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

Euklid's GCD (and LCM) algorithm

Literature

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

Addison-Wesley, 1973

---