help with Performance on this Java Code

code
java
performance

#1

link text

I am not able to Pass the last 3 test cases as it exceed 5 Seconds
Can someone Help me Solve this Problem

Some Expert has suggested Sieve of Etheneous Solution but Unable to Code into this

also there is a link that explains the mathematical Part of it
http://bababadalgharaghtakamminarronnkonnbro.blogspot.com/