- Assignment #2 50 Points
- Use only the instructions of chapters 1-8, i.e. absolutely no recursion
- For this assignment
- A prime number is a positive integer divisible only by itself and 1. There are several ways to find prime numbers, and also to determine whether or not a number is prime. One method to determine whether or not a positive integer N is prime is to simply determine if there is any integer K <= N / 2 such that N % K == 0. In such a case, N is not prime. Unfortunately this means that you must divide N by up to N/2 different values. A more efficient method relies on two facts. First, the smallest divisor K such that K % N == 0, meaning N is not prime, must also be a prime number. Second, for such a value K, it must be <= square_root(N).
- In this problem, we will build a class called PrimeNumberTester. While the major function of an object of this class is to determine whether or not a number is prime, such an object will also create and hold an array of prime numbers which will be used to determine if a number is prime. In addition to using a class to solve this problem, you will also be expected to separate class specification from the implementation and client code (see page 424 of the text). In other words, you should have a file PrimeNumberTester.h which holds the prototypes and attributes for the class; a file PrimeNumberTester.cpp which holds the method definitions (implementation) for the class, and a main.cpp file which is the driver program. Your main() program should execute as follows:
- In a while loop, ask the user to input an integer 1 < MAX <=4000 or -1, where MAX is the maximum number of primes to be created. Remember, this is not the maximum prime number to find but the number of primes to find. This is the list of prime numbers that need to be used in determining whether or not a number is prime. In the PrimeNumberTester class (PNT) there will be a member attribute called primeNumberList that holds the first MAX prime numbers. If -1 is input, the program should terminate. Thus, when main() starts and reads a value for MAX, in creating an object of class primeNumberTester it will initialize the array primeNumberList with the first MAX prime numbers. If the input value is not legal, i.e < -1 or > 4000, remain in the loop until a legal value is input. You do not need to consider if the value input is too large as an integer itself.
- Note: Since we are only concerned with up to the first 4,000 primes, we can use an integer array to store the primes.
- Assuming that the terminate option has not been input. Main() should next, in an inner while loop, ask the user to input a -1, 0, or 1:
- (-1) terminate the inner most while loop. This would cause the program to move “up” to the containing outermost while loop, destroy (call its destructor) the current object, and again ask the user to input a new MAX value.
- If a 0 is input, the program should output the list of primes currently stored in primeNumnberList, and then again ask for an input of -1, 0, or 1.
- If a 1 is input, the program should ask the user to input an integer (N) which is to be tested to determine whether or not it is prime. The value N must be >1. Using N and the primeNumberList, the program should use the just described algorithm to determine whether or not N is prime. If N is prime, the program should output that it is prime. If N is not prime, the program should output the value of the smallest prime divisor. In the case in which sqrt(N) is larger than the largest prime in primeNumberList, the program should still test the first MAX primes as divisors. In this case, if a divisor is not found it should output that the test failed but sqrt(N) was > MAX and so the search was terminated early, and thus not conclusive.
- The following is an example run of the program. It does not thoroughly test the program so beware.
- User input is in RED.
- Welcome to the Prime Number Checker Program
- Input the maximum number of primes for the prime number table
- (must be > 1 and <= 4,000) or -1 to quit: 5
- Creating table of the first 5 prime numbers
- Table created
- Input:
- -1 to create a new prime number table or quit
- 0 to output current table of prime numbers
- 1 to determine if a number is prime: 1
- Input a value to check for prime (> 1): 29
- 29 is prime
- Input:
- -1 to create a new prime number table or quit
- 0 to output current table of prime numbers
- 1 to determine if a number is prime: 0
- The list of primes in the prime number table is as follows:
- 2
- 3
- 5
- 7
- 11
- Input:
- -1 to create a new prime number table or quit
- 0 to output current table of prime numbers
- 1 to determine if a number is prime: 149
- No primer divisor found up to MAX of 11. The value 149 may or may not be prime.
- Etc………