Help with Problem 61 Prime Numbers Generation

> 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?