LAB ASSIGNMENT 4
Prime numbers are integers that have only two multiplicative factors:
themselves and one. For example, the first five prime numbers are 2,
3, 5, 7 and 11 (1 is not prime since it has only one factor: namely,
the number 1). The Fundamental Theorem of Arithmetic shows that the
primes are the building blocks of the positive integers: every
positive integer is a product of prime numbers in one and only one
way.
Prime numbers have many applications including cryptography (the
coding of information for the purposes of securing content). One
common type of cryptography uses a pair of prime numbers, one that is
used in the formulation of the encryption key and another that is used
in the decryption key. In order to make more robust cryptographic
algorithms, bigger and bigger prime numbers are desired. Your task
today will be to a) determine which of a given set of numbers are
prime numbers AND b) determine which numbers in a range of numbers are
prime.
If a number is prime that means that there are no smaller numbers than
the number that divide evenly into it, other than one. For example,
assume we wish to test if the number 11 is prime. We successively test
to see if 10, 9, 8, 7, 6, 5, 4, 3 or 2 divide evenly into 11; clearly,
none do, and hence, 11 must be prime.
A little more thought reveals that we did not have to test all the way
down to 2, for if this were a factor, a larger number would have
already successfully divided evenly. This is easy to see for an
example of 10; we do not have to test down to 2 since the test for the
factor 5 already identified the number 2 as a factor. In fact, we only
need to test down to the truncated square root of the number we wish
to test (this is true only if the number we are testing is greater
than 3 - i.e. if you want to test 66, you only need to test if 66 is
divisible by numbers from 65 to 8). The test for whether one number
divides evenly into another can be preformed easily using the modulo
operator (%).
Steps to determine if number, n, is prime:
1. Declare variables in main: start, stop, prime_flag, current_number
2. Read in number to check from file or user, n.
3. Set prime_flag=1, i.e. assume that the number n is prime
4. Set start = n-1; and stop = (int)floor(sqrt(n));
5. Use current_number to loop from start to stop and check if
n%current_number evaluates to 0.
6. If the remainder is equal to 0 print out the intermediate factors
and reset the prime_flag to 0.
7. Check the value of the prime_flag, if its 0 declare the number not
a prime number else declare it a prime number.
Assignment Part a: lab4a.c
You are to create a program that will read in a list of integers from
a file, and test to see if each number is prime. You must run your
program one time for the entire number set. Test for EOF (or use the
function feof()) to know when to stop processing (see the example
feof.c posted on the course web site). You are to determine if each
integer read is prime or not, and output the result to stdout.
If a number is prime, your output should read:
101 = 101 x 1
101: PRIME Number
For a number that turns out not to be prime, your output should read:
333 = 333 x 1
333 = 111 x 3
333 = 37 x 9
333: NOT A PRIME Number
Assignment Part b: lab4b.c
Revise your program of lab4a.c to handle a range of integers as
specified by the user. For example, the user can request the program
to find all prime numbers in the range of 900 to 1000. Your output
should now just list ONLY the prime numbers in the given range and NOT
the intermediate factors OR the numbers that are not prime. Only test
for ranges that have a start number greater than 3. Remember to
include error checks and COMMENT your code.
Deliverables (please staple and don't forget your name):
Printout of both lab4a.c and lab4b.c source code files.
Printouts of the results from parts (a) and (b).