Program 4 - Super Sieve

Summary

This program is a variation of the Sieve of Eratosthenes for finding prime numbers described in Section 22.1. The concept of primality applies to many algebraic structures and not just to the integers and so this program includes a generic form of the sieve and three instantiations.

One instantiation gives the normal primes and so is based on the type Integer.

The second is based on complex or Gaussian integers of the form p + iq where p and q are integers and i is of course the square root of minus one.

The third is based on polynomials whose coefficients are integers modulo 2, that is can only be zero or one. Examples of such polynomials are x + 1 and x³ + x + 1.

The program asks the user to identify the kind of primes to be searched for and how many values to test. It prints the primes as they are found and concludes by noting the total number found.

The generic package Eratosthenes contains the various tasks. It has a number of generic parameters defining the algebraic structure. There is also a private generic package Eratosthenes.Frame containing the interface to the display mechanism. In this demonstration exercise the display mechanism is simplified to just printing out each new prime on a new line but the interface is retained for compatibility with the example in Chapter 22.

There are then three packages Integer_Stuff, Complex_Stuff and Poly_Stuff containing the types and subprograms required for the three algebraic structures. These are followed by three corresponding instantiations of the generic package Eratosthenes which are Integer_Sieve, Complex_Sieve and Poly_Sieve.

Finally, the main subprogram calls the procedure Do_It of the instantiation of Eratosthenes according to the algebraic structure chosen by the user.

generic

type Element is private;

Unit: in Element;

with function Succ(E: Element) return Element;

with function Is_Factor(E, P: Element) return Boolean;

with procedure Put(E: in Element);

package Eratosthenes is

procedure Do_It(To_Try: in Integer;

Found: out Integer);

end;

private generic

package Eratosthenes.Frame is

type Position is private;

procedure Make_Frame(Prime: in Element; Where: out Position);

procedure Write_To_Frame(Value: in Element; Where: in Position);

procedure Clear_Frame(Where: in Position);

private

type Position is null record;

end;

with Ada.Text_IO;

package body Eratosthenes.Frame is

procedure Make_Frame(Prime: in Element; Where: out Position) is

begin

Ada.Text_IO.New_Line;

Put(Prime);

Where := (null record); -- null aggregate

end Make_Frame;