Suppose when searching for a large prime, our first step is tosieve by eliminating the first n primes. How large should n be tospeed up our search by a factor of 10? This requires carefulthought and inventiveness before doing a computation.
How to approach this: Eliminating all odd numbers speeds up ourprogram by a factor of 2, since we've eliminated half of thechoices that are composite. If we also immediately disqualifymultiples of 3, then we speed up our program by a factor of 3,since we have eliminated 2/3 of all composites. Check that thatargument is correct. Now see what happens when you eliminate all of2, 3 and 5. Again for 2,3,5,7. Now try to figure out themathematical result and use it to solve for n.
