# SLUG Mailing List Archives

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

• To: Some Linux Users Group <slug@xxxxxxxxxxx>
• Subject: Re: [SLUG] c++... a bit OT
• From: Peter Chubb <peterc@xxxxxxxxxx>
• Date: Wed Nov 15 16:53:07 2000

```>>>>> "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;
}

```