CSC 271
Homework 4 in C++

Assigned Oct 25, due Nov 1

Write a program that generates a list of all the prime numbers up to a specified limit.

That's a moderately interesting problem in its own right, but since I have specific things I want to teach with it, I'm going to be very specific about how the program is to be structured.

• Your main program, which should be in the file primes.cpp, should call the getSize function to ask the user for a limit. The main program should then set up an array of ints the appropriate size, call the sieve function with that array, and then call a printResults function with that array.
• The sieve function, which should be in a separate source code file sieve.cpp, will take in an array of N ints and fill them in as follows: if J is prime, then arr[J] should be zero. If J is composite, then arr[J] should be a nontrivial divisor of J, i.e. an integer greater than 1 and less than J that divides J.
• The getSize function and the printResults function should both be in another source code file primesIO.cpp. The former should ask the user for a size, check it for reasonableness, ask the user again if it wasn't reasonable, and once it's got a reasonable size, return it. (You might also want a way for the user to cancel and get out.) The latter should take in an array of ints, and print out a line for each entry in the array, of one of the two forms

  17 is prime

  or

  20 has prime divisors 2 2 5

  which it figures out by calling divisors; see below.
• The divisors function, which should be in a separate source code file divisors.cpp, takes in a number and the sieve array, and returns a list of divisors (including multiples, as in the case of 20 above). Unfortunately, C++ doesn't have a built-in "list" data type, so we need another way to do things. You could return a linked list, but that requires dynamic memory allocation, which we haven't seen yet. You could return an array, but as we saw on Oct. 20, "returning an array" is problematic in C++; a safer course is for the calling function to allocate an array as big as might be necessary, then pass the size and address of that array to another function to fill in. You could even put the numbers into a string, separated by spaces or commas.