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.
primes.cpp, should call the
getSizefunction to ask the user for a limit. The main program should then set up an array of ints the appropriate size, call the
sievefunction with that array, and then call a
printResultsfunction with that array.
sievefunction, 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.
getSizefunction and the
printResultsfunction 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 primeor
20 has prime divisors 2 2 5which it figures out by calling
divisors; see below.
divisorsfunction, 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.