Prime numbers

by Stephen R. Schmitt

Generating prime numbers

An integer greater than one is a prime number if its only divisors are itself and one. Non-prime numbers are called composite. The number 18 is composite; it is a composite of 2×3×3. The number 19 is a prime number.

One way to generate prime numbers is to test each number to see if it can be factored by all of the odd numbers up to the square root of the number being tested. It is not necessary to test above the square root of the number since all other combinations of factors would include one number larger than the square root, and one smaller. That is, it would be superfluous to check numbers larger than the square root.

Zeno source code

• Download Page

program

    var prime : int
    var i, j : int
    var sqrtp : int
    var notprime : boolean

    put 2 : 6 ... 
    put 3 : 6 ... 
    prime := 5                      % start at 5
    j := 2
  
    repeat
     
        sqrtp := round( sqrt( prime ) + 0.5 )
        notprime := false
        i := 1                      % start test at one
    
        while not ( ( i >= sqrtp) or ( notprime ) )
            i := i + 2  
            notprime := prime mod i = 0
        end while

        if not notprime then        % is a prime number
            incr j
            put prime : 6 ...
            if (j mod 5) = 0 then   % start new line
                put ""
            end if
        end if

        prime := prime + 2          % next trial, skip even numbers

    until prime > 5000

end program

Sample output

     2     3     5     7    11 
    13    17    19    23    29 
    31    37    41    43    47 
    53    59    61    67    71 
    73    79    83    89    97 
   101   103   107   109   113 

AbCd Classics - free on-line books