CMSC 222 Discrete Structures Example Project Examples of Good and Bad Write Ups EXAMPLE PROJECT Write a program that reads integers one at a time from an input text file named integers dat tests each integer to determine whether or not it is prime and writes an appropriate result to standard output You can assume that the input integers are restricted to values between 2 and 231 1 inclusive and that the input file has one integer per line On output your program should echo each input integer right justified with the is aligned as indicated below followed by a statement indicating whether or not the integer is prime and if not an indication of what the smallest prime factor is For example if the file integers dat contains 2 3 4 5 1234 3989 4481923 15824363 46327 46337 2146654199 1772941421 2147483645 2147483647 then the corresponding output of a correct program would be 2 3 4 5 1234 3989 4481923 15824363 46327 46337 2146654199 1772941421 2147483645 2147483647 is is is is is is is is is is is is is is prime prime not prime prime not prime prime not prime not prime prime prime not prime not prime not prime prime 2 is the smallest prime factor 2 is the smallest prime factor 1607 is the smallest prime factor 3967 is the smallest prime factor 46327 is the smallest prime factor 1201 is the smallest prime factor 5 is the smallest prime factor EXAMPLE OF A GOOD WRITE UP Overview Recall that by definition a prime number is an integer greater than 1 that is evenly divisible only by 1 and itself The purpose of this project is to implement a correct and efficient algorithm to determine the primality of a list of numbers For those numbers in the list that are not prime the algorithm must also determine the smallest prime factor Background The solution implemented herein is based on the Sieve of Eratosthenes Given an integer n 1 the Sieve computes all primes between 2 and n The Sieve can be represented by the following psuedocode assume all integers 2 n are prime for k 2 k b nc k if k is prime for s 2 s n k s sk is not prime The Sieve begins by assuming that all integers between 2 and n are prime Because k 2 is prime the algorithm proceeds to eliminate all multiples of 2 from the collection of primes i e sk is not prime where k 2 and s 2 3 n 2 Because k 3 is prime the algorithm then proceeds to eliminate all multiples of 3 Because k 4 is not prime it was eliminated as a multiple of 2 it is not considered The algorithm then eliminates all multiples of k 5 This process continues until k b nc at which point the algorithm has determined all primes between 2 and n Note that the algorithm needs to only evaluate k b nc because if any composite number has a factor greater than b nc then it must have a corresponding factor less than b nc Algorithm Because the integers in the file are guaranteed to be no larger than 231 1 ideally we would like to construct a list array of 231 1 integers and execute the Sieve on this array However memory limitations preclude the use of an array of this size Alternatively we could use the Sieve to create a linked list that contains only the primes from 2 to 231 1 and then divide any given integer n by only the primes from 2 to b nc Note however that this implementation will frequently require us to perform redundant computations For example if n 31 our algorithm would divide by the primes 2 3 and 5 even though the Sieve would have already determined 31 to be prime Instead we choose to implement an array indexed from 2 to b 231 1c 46 340 certainly within memory limitations and execute the Sieve on this array We initialize each array element to be 1 As the Sieve eliminates multiples sk of a prime factor k we enter that prime factor k as the entry into array element sk only if the array element was 1 This process ensures that each array element will be a 1 if the corresponding index is prime or the smallest prime factor of the corresponding index if the index is not prime For example consider that 6 has both 2 and 3 as prime factors but 2 is the smallest prime factor we do not overwrite the 2 already in the 6th array element when eliminating multiples of 3 The array would appear as follows 1 2 1 3 2 4 1 5 2 6 1 7 2 8 3 9 2 10 1 11 2 12 149 46 339 2 46 340 Therefore the primality of any integer n 46 340 can be determined via direct lookup in the array if n is not prime the nth array element contains the smallest prime factor If instead n 46 340 we only need to divide by those primes less than b nc clearly denoted by 1 s until the first encountered prime divides n evenly thereby determining the smallest prime factor If no such prime divides n evenly n is prime The algorithm is described by the following pseudocode functions void initializeArray int primality set primality i 1 for i 2 3 SQRT MAX for int k 2 k b nc k if primality k 1 for s 2 s n k s primality sk k bool isPrime int n int primality int factor if n SQRT MAX if primality n 1 return true else factor primality n return false else for int k 2 k SQRT MAX k if primality k 1 n mod k 0 factor k return false return true Efficiency The algorithm described above is not optimal in terms of space or time Our approach requires us to store an array of at least 46 339 elements a space optimal algorithm would require no storage By its design our approach also discards information that could have easily been determined when the Sieve is first applied to the array i e the primality of integers greater than 46 340 Nonetheless the approach is easy to implement and understand and its execution time is modest even for files containing large integers Correctness Testing Since the project description stated that I could assume that the input integers are restricted to values between 2 and 231 1 inclusive and that the input file has one integer per line I did not test my program using any integers outside that range nor with an input file that was not to specifications In order to test the algorithm I first ran my program on the provided integers dat file the results from my program were the same as those shown in the project description Because the provided file was such a small example I then decided to test my program on all integers between 2 and 231 1 inclusive Using the Web site http www prime numbers org …