Code : [click][1]

Since there are 9592 prime numbers between 1 to `n`

, I have declared an array `a`

having 9592 elements. We know that `2`

and `3`

are primes so I have stored them in the array directly. Starting from `4`

till `100000`

, each number `i`

is checked for divisibility starting from `j = i / 2`

till we find a number which divides `i`

. When such a number is found, we know that `i`

is not a prime and so `a[n]`

(starting from n = 2) is assigned a value of -1 and `n`

is incremented by `1`

. If `i % j != 0`

, variable `u`

is incremented by `1`

. For each `i`

, `if (u == (i / 2) - 1)`

, `i`

is stored in the array `a`

because it’s a prime. (not divisible by any number in the range `i / 2`

to `2`

)

[1]: http://ideone.com/9ktYpM