Re: [SLUG] c++... a bit OT

[Peter Chubb <peterc@xxxxxxxxxx>]

>>>>> "James" == James Wilkinson <jamesw@xxxxxxxxxxxxxxxxxxx> writes:

James> This one time, at band camp, Alex Salmon said:
>> what do u mean by that exactly 3 to sqrt(x) by 2... what is x 

James> if (num % 2 == 1) {
James> 	for (i = 3; i <= sqrt(num); i+=2) {
James> 		test;
James> 	}
James> }


You only actually have to test against the primes you've already
found.

So if you store them in an array, you can do something like this:

const int nprimes = 10000;
uint64_t primes[nprimes] = {1, 2, 3, 5, 7, 11,};
int lastprimeIdx = 5;

bool_t isPrime(uint64_t num)
{
	for (int i = 2; i <= lastprimeIdx; i++)
	    if (num % primes[i] == 0)
	        return false;
        primes[++lastprimeIdx] = num;
	return true;
}

int main()
{
	uint64_t maybePrime;

	for (maybePrime = primes[lastprimeIdx]; 
	        lastprimeIdx < nprimes; maybePrime += 2)
	    isPrime(maybePrime) && cout << maybePrime << "\n";
	return 0;
}