Concerning your algo, try sieve of Eratosthenes. Usually it's right answer when we need to create table of primes for some segment.