EWD249 - 44

problem when "give for odd j to jprime the meaning: j is a prime number" -call it "2b2(3)a"- occurs among the well-understood repertoire. We now assume that it does not, in other words we have to evoke a computation deciding whether a given odd value of j has a factor. It is only at this stage that the algebra really enters the picture. Here we make use of our knowledge that we only need to try prime factors: furthermore we shall use the fact that the prime numbers to be tried can already be found in the filled portion of the array p.

We use the facts that

1. j being an odd value, the smallest potential factor to be tried is p[2], i.e. the smallest prime number larger than 2

2. the largest prime number to be tried is p[ord-1] when p[ord] is the smallest prime number whose square exceeds j

(Here I have also used the fact that the smallest prime number whose square exceeds j can already be found in the table p. In all humility I quote Don Knuth's comment on an earlier version of this program, where I took this fact for granted:

"Here you are guilty of a serious omission! Your program makes use of a deep result of number theory, namely that if p_n denotes the n-th prime number we always have

p_{n+1} < p_n^2   ."

Peccavi.)

If this set is not empty, we have a chance of finding a factor, and as soon as a factor has been found, the investigation of this particular j value can be stopped. We have to decide in which order the prime numbers from the set will be tried, and we shall do so in order of increasing magnitude, because the smaller a prime number the larger the probability of its being a factor of j.

When the value of ord is known we can give for "give for odd j to jprime the meaning: j is a prime number" the following description on level 2b3(3):

2b2(3)a  =
begin integer n; n:= 2; jprime:= true;
      while n < ord and jprime do
      begin "give to jprime the meaning: p[n] is not a factor of j"; n:= n + 1  end
end