Oh, then store the numbers of found primes and loop till you have found the nth prime.
Oh, then store the numbers of found primes and loop till you have found the nth prime.
If the max length of the array is 256, then you cannot "calculate more primes on demand", at least not enough to reach 1000 times and thereby use the incredibly easy solution that I described. It also rules out the sieve of Eratosthenes.Originally Posted by megazord
But what you can do is this: observe that the 1000th prime is 7919. Therefore, all composite numbers less than the 1000th prime have a prime divisor no greater than the square root of the 1000th prime, which is a little less than 89. 89 is the 24th prime (so actually you only need the first 23 primes). So, when you are doing trial division, you only need to test with these 23 primes. If the number does not have a divisor among these, the number must be prime.
Another thing to do: skip all the even numbers greater than two.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)