The trick here is to realize that for a given number (n), if no currently discovered primes divide sqrt(n), then (n) itself is prime. Be sure to use efficient data structures to store found primes (a flag array of size (n) should do). You can also divide the array into subarrays of optimal cache size to achieve better locality.