This portion of the program is independent of the specific implementation of the data abstraction. It does not have to be changed if the implementation of the data abstraction changes. Candidates is an instance of the data structure of type collection.
primes(n)
/* Prints all prime numbers between 2 and n */
int n;
{
collection candidates;
create(n,candidates);
remove(n,candidates);
print(n,candidates);
}
create(n,c)
/* Creates a collection of integers between 2 and n */
int n;
collection c;
{
int i;
set(n,c);
for (i=2;i<=n;i++)
insert(i,c);
}
remove(n,c)
/* Removes all nonprimes from c */
int n;
collection c;
{
int firstprime;
int factor;
firstprime = 2;
factor = firstprime;
while (nonprimes(factor,n))
{
delete(factor,n,c);
factor++;
}
}
nonprimes(factor,n)
/* Returns true only if non
primes may remain in c
*/
int factor,n;
double sqrt();
{
return(factor <= sqrt((double)n));
}
delete(factor,n,c)
/* Deletes multiples of factor from c */
int factor,n;
collection c;
{
int nextmultiple;
nextmultiple = 2 * factor;
while (nextmultiple <= n)
{
omit(nextmultiple,c);
nextmultiple = nextmultiple + factor;
}
}
print(n,c)
/* Prints integers in c */
int n;
collection c;
{
int i;
for (i=2;i<=n;i++)
if (belongs(i,c))
printf("\n %d\n",i);
}