DO NOT READ THIS FILE UNTIL YOU ARE STUCK!!


Having trouble with Part B on Project 1?  Maybe this will help.


The Part B program has to find the primes between I and J.  For
example, suppose I = 10^8 and J = 10^8 + 10^6.  Let L = sqrt{J}.
The program has a "for each p" loop that has to run through all
primes p < L.  This is because the primes between 10^8 and
10^8 + 10^6 are precisely the numbers bewteen 10^8 and
10^8 + 10^6 that are not divisible by any prime p < L.

The fastest way to find the primes p < L is to use the program
of Part A.
This program makes a table P[] so that p is prime iff P[p]=1.

Here is a suggested way to do Part B efficiently.

  L = sqrt{J}; 
  Copy and use the Part A program with its J = L to create P[]
Now, for 0<j<L, j is prime iff P[j]=1.

  char A[10^6];  // Save space; you don't need char A[10^8+10^6]
  for (i=0; i<10^6; i++) A[i]='1'; // initialize A; A[i]=1 will mean I+i is prime

Implement the "for each p" loop as:
  for (p=1; p<=L; p++) {
      if (P[p] == 0) continue; // skip the non-prime p
      i = least multiple of p that is >= I  // Remember what I said in class
      while (i < J) { A[i-I] = '0'; i=i+p } // mark multiples of p as composite
      }

Then, for I < i < J, i is prime iff A[i-I]=1.
Count and print as needed.

A useful resource for checking your answers is  www.factordb.com .

NOTES: The two input numbers should be on one line separated by one space.
The two primes in output should be on one line separated by one space.
There should be exactly one \newline character after the last prime output.
If Vocareum gives you 0 points, you have a problem other than speed.
If Vocareum gives you some but not all points, you have a speed problem.
Another suggestion that sometimes works is to compile your code on
Vocareum before submitting it.
The TAs notice that some students write redundant lines of code.  Please
remove them before showing your program to the TAs.

Good Luck!

SSW