Help with Problem 61 Prime Numbers Generation

Back to General discussions forum

Christopher Matthews     2014-10-29 18:49:43

I'm having a bit of trouble understanding the algorithm for the Prime Numbers Generation problem; I'm not looking to have the answer given to me, just a push in the right direction. Would anybody mind helping to explain the implementation of the algorithm for me? I understand that I'm supposed to begin by looping through all odd numbers up to 'n', but how do I know what 'n' is, since the only information given in the test cases is the indexes of the primes I'm supposed to print? Then, I'm supposed to try to divide each odd number by each prime less than sqrt(m), but what about the numbers that don't satisfy that condition? Are they composite? I'd really appreciate a clear explanation...

Thanks in advance, Christopher P. Matthews

Rodion (admin)     2014-10-30 05:17:44
User avatar

> looping through all odd numbers up to 'n', but how do I know what 'n' is, since the only information given in the test cases is the indexes of the primes I'm supposed to print

Well, then how about looping and filling some array or list with primes you find until the size of this list is greater than the largest index you are asked about? E.g. if you are asked about 100-th, 57-th and 318-th - then write down say 318 (or more) and pick the one you need...

> to divide each odd number by each prime less than sqrt(m), but what about the numbers that don't satisfy that condition? Are they composite?

Let's see:

  • even numbers (larger than 2) are divisible by 2 and hence are composite anyway, so we skip them;
  • you need not try to divide by values other than primes because if the number X is divisible by some composite C - and that means the C is divisible by at least some prime P - then X is divisible by P too (say X=C*D and C=P*Q then X=(P*Q)*D);
  • you need not divide by values exceeding sqrt(m) because if divisor of m is greater than sqrt(m) then the quotient is less, e.g. if m/p=q and p>sqrt(m) then q<sqrt(m) (otherwise their product should be greater than m). But since it is less and m is also divisible by this quotient, then you already tried it (if it is prime) or one of its divisors (if composite).

Does this short explanation make sense?

Please login and solve 5 problems to be able to post at forum