---

CIS071 Lab10 – Finding Prime Numbers DUE: 10AM, Nov 08, 2006

---

Objectives:

Finding all prime numbers smaller than N = 10,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 smaller than N = 10,000, and print them on screen.

Implementation:

PROGRAM 1: Simple Approach

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 N²/2 remainder calculations (can you see why?).

PROGRAM 2: More Efficient Approach

Create an array of integers called primes (int primes[10000]) where we will store all primes larger than 1 found by the program

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. Run the programs and check if they work correctly by comparing to the first 30 primes given above. 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.