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

[Peter Chubb]

>>>>> "James" == James Wilkinson <[EMAIL PROTECTED]> 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;
}


-- 
SLUG - Sydney Linux User Group Mailing List - http://slug.org.au/
More Info: http://slug.org.au/lists/listinfo/slug