Assignment #6

Due Monday 3-5-2001 at 3:30 PM

Part One - Sieve of Eratosthenes

A prime integer is any integer that is evenly divisible only by itself and 1. The Sieve of Eratosthenes is a method of finding prime numbers. It operates as follows:

List the integers from 1 to n. You already know that 1 is prime. Starting with 2, cross out every number that's a multiple of 2. (Do not cross out 2; only cross out multiples beyond the number you're working on.) Move on to 3, and so forth: each time you come to a number that isn't crossed out, cross out all of its multiples. When there are no more numbers to be crossed out, the remaining numbers in the list are all the primes between 1 and n.

(There was an example use of this algorithm on the printed copy of this assignment, but I don't think I can html-ize it very easily. See me if you have questions.)

Part One Requirements

Write a program that uses this algorithm and an array of 1000 elements to find the primes between 1 and 999. (Ignore element 0 of the array.)

A design document is required for this assignment. Remember to turn in your printed source code and output, and an electronic copy of your program.

Since there's going to be more than one screenful of output all at once, the easiest way to get the output is to capture it in a file. In order to do this, you need to run your program from the command line (not directly from the compiler, nor by double-clicking on the .exe). When you run it, do so by typing (for example) "hw6 > output.txt". This creates the file "output.txt" in the same directory as your executable.

The following is what I captured from the MS-DOS prompt window when I did this: 


C:\WINDOWS>cd desktop

C:\WINDOWS\Desktop>cd work

C:\WINDOWS\Desktop\Work>cd hw6

C:\WINDOWS\Desktop\Work\hw6>cd debug

C:\WINDOWS\Desktop\Work\hw6\Debug>hw6 > output.txt

C:\WINDOWS\Desktop\Work\hw6\Debug>

Part Two - Dot Products

Write a function that accepts two arrays, signifying mathematical vectors, and returns their dot product. Write a main program that gets the vectors from the user and calls this function.

The dot product of two vectors, Va = {a1, a2, ..., an} and Vb = {b1, b2, ..., bn} is

Va · Vb = a1 * b1 + a2 * b2 + ... + an * bn
The dot product is only defined for two vectors of the same length; however, if you have two vectors of different length, the short one may be padded with zeros to the length of the longer one.

Part Two Requirements

Design documentation is not required for this part of the assignment.

Your function should accept arrays of any size, remembering the definition of the dot product, but the main program may accept only one size of array.

You can consolidate the two parts of your assignment (i.e., write one program that asks whether you'd like to find primes or calculate a dot product) if you'd like, but you don't have to.

Back to Main Page