Setup

1. [c]

   On a CS lab or classroom machine in the RNS Link, create a subdirectory to hold your work on this assignment, as follows.

   • Log in (not to mist or helios, but just to a CS lab or classroom machine).

   • % cd ~
     % mkdir PDC
     % mkdir PDC/hw1
     % cd PDC/hw1
     

     (Don't enter the % sign: it stands for the csh shell prompt on a CS lab or classroom machine.)

Prime numbers

1. [hc]

   Write a program primes.C that determines the prime numbers between 2 and N=1000, inclusive, using the following Sieve of Eratosthenes approach.

   Note: Recall that a prime number is an integer greater than 1 that is divisible by only 1 and itself. We say that integer a divides integer b if b is divisible by a, i.e., a × m = b for some other integer m.

   Write the following steps out on paper, first:

   1. Create an array num of N bytes, all initialized at 1 except num[0] = num[1] = 0. (The value 1 will represent true, and 0 will represent false.)

   2. Define an int variable p for holding one prime number. Invariant: At all times, if k > 1 then num[k] will indicate whether there is some prime less than p that divides k.

      Initialize p at the smallest prime number, 2 (so the invariant will be true at the outset).

   3. Next, write a nested loop to "mark out" non-primes divisible by p.

      • The inner loop should set num[p*i] = 0 for i=2, 3, ..., until p*i≥N. This marks each number p*i as a non-prime.

      • The outer loop should perform the inner loop for each prime p, starting with p=2. After performing the inner loop, the next prime will be the first index k>p such that num[k] == 1.

      Note: This outer loop can obviously stop when p>N. In fact, it can stop as soon as p>sqrt(N) (can you explain why?).

   4. Finally, write a C++ main() that defines the variables num[] and p, carries out the nested loop, then prints all numbers k such that num[k]=1 after the nested loop. The output will be the primes between 2 and N, inclusive

      2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
      

   Now implement your program on a CS lab or classroom computer.

2. [c]

   Use your program primes.C to determine how many primes are there between 2 and 1,000,000, inclusive

Delivery

Homework, labs, and projects will all be submitted using git, a widely used revision control/repository system. The CS-managed stogit server already contains a repository pdc-i15/username for your St. Olaf username

1. First, on a Link computer, carry out steps 1 to 3 only of this document. This enables you to perform git operations from the command line without entering your password each time.

2. Next, connect your ~/PDC directory to your stogit repository as follows:

   %  cd ~/PDC
   %  git init
   %  git remote add origin git@stogit.cs.stolaf.edu:pdc-i15/username.git
   

   This only needs to be done once to associate your ~/PDC directory to your git repository.

   Note: Check your work carefully on the git remote add command above.

   • You can check the remote repository your directory is currently associated with using

     %  git remote -v
     

   • If you find you have made a mistake and you need to associate with your directory with a different remote repository, enter

     %  git remote remove origin
     

     then perform another git remote add command.

3. Finally, add your files to your repository on stogit using these commands:

   %  cd ~/PDC
   %  git add -A
   %  git commit -a -m "HW1 submission" 
   %  git push origin master