I originally solved this problem in Java
Now, I have also solved it in C, so that you can understand.
Here’s the link: http://www.codechef.com/viewsolution/4170528
I have divided the problem into functions,
Check out the first function void generate_primes(), observe it carefully and try to understand.
This function generates the primes till the sqrt(1030000)
It generates the primes by checking if a number is divisible by any prime number less than the square root of the number. It uses the generated primes side by side for performing this check.
Firstly, we store pr=2, After this all primes are odd,
so no need to check for even. That’s why the for loop starts from 3 and has an increment of 2.
Now lets execute this code, step by step:
i=3, pr * pr< = i is false, loop not executed, f==0
So pr=3 is assigned
i=5, pr*pr<=i is true, loop executed, but condition i%p[j] (i%2) is false
pr * pr<=i is false, f still 0.
So, pr=5 is assigned.
Similarily execute it for 5-6 more values manually.
Now you have the primes in the array pr, so to check if a number is prime, check for divisibility by the primes less than the square root of the number. No need to check all the numbers till the number or till sqrt(number).<Br><Br><BR>
**Do not copy the code, try to understand it and then code it yourself.**