CIS071
Lab10 – Finding Prime Numbers DUE:
noon, Apr 03, 2007
Objectives:
Finding all prime numbers
smaller than N = 100,000.
Prime Numbers:
In mathematics, a prime
number (or a prime) is a positive integer that has exactly two divisors, which
are 1 and the prime number itself. For example, 4 is not prime number because
it is divisible by 1, 2, and 4. On the other hand, 5 is prime number because it
is divisible only by 1 and 5. The first 30 prime numbers are 1, 2, 3, 5, 7, 11,
13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
101, 103, 107, 109, and 113.
Task:
You should write two programs
that both find all prime numbers between 1 and N, where N < 1,000,000, and
print them on screen.
Implementation:
PROGRAM 1: Simple Approach
Ask
user to enter N
Numbers
1 and 2 are prime, print them on screen
Repeat
the following procedure for each number i
between 3 and N:
Find the remainder of division of i by all numbers between 2 and i-1 (remember that operator ‘%’ finds the remainder of
division, e.g., 11%3 equals 2)
If all remainders are different from zero, the
number is prime; if at least one of the remainders equals zero, the number is
not prime (Hint: to save time, as
soon as one of the remainders is zero, you can start examining the next
number);
If the number is prime print it on screen.
Hint: you
can implement this algorithm by a nested loop
Note: This
approach is not very efficient, since it requires about N2/2 remainder calculations (can you see why?).
PROGRAM 2: More Efficient
Approach
Create
an array of integers called primes (int primes[1000000]) where we will store all
primes larger than 1 found by the program
Ask
user to enter N
Store
number 2 in primes array
Print
numbers 1 and 2 on screen
Repeat
the following procedure for each number i
between 3 and N:
Find the remainder of division of i by all primes in the array primes
If at least one of the remainders equals zero, the
number is not prime. As soon as the remainder is zero, you can increment i by one. If all remainders are
different from zero, the number is prime
If the number is prime, add it to the array primes, and print it on screen
Hint: you
can implement this algorithm by a nested loop
Note: This
approach is not more efficient than the previous one (can you see why?).
The output of both
programs should look like:
All
prime numbers between 1 and 10000 are:
2,
3, 5, 7, 11, 13, 17, 19, 23, 29,
31,
37, 41, 43, 47, 53, 59, 61, 67,
71,
73, 79, 83, 89, 97, 101, 103...
Testing:
Make sure your programs
compile. Enter N = 1000. Run the programs and check if they work correctly by
comparing to the first 30 primes given above. Enter increasingly large values
of N, i.e. explore what happens when N = 10,000, N = 20,000, N = 50,000, N =
100,000, N = 200,000, N = 500,000, and N = 1,000,000.Use your watch to measure
how much time it takes for your programs to finish. Report the times.
Deliverables:
Submit your program; attach results of test runs of the program, provide brief answers about the speed of the programs.