Dynamic programming (testing divisibility by the primes already found) would greatly improve the algorithm. And of course sieving is absurdly fast compared to checking primality individually.