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
Addison-Wesley, 1973


Cover Contents Index Main page

last modified 1st August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic