Hi i''ve been looking for a way to write a isPrime(int x), but have only found abstract ways to solve to problem. Is there an easy way to do it? Thanks!

Hi there,
This is how i do it, its prob the slowest way, but it works, shouldn''t have any problem at all chewing through numbers up to 1 mil, i think it starts to get slow when going through numbers up to 8 digits and more.

Shabadoo

bool isPrime( __int64 num ){ if( num == 3 ) { return true; } __int64 sr = sqrt( num ); //if modding by even number there will always //be a remainder as the primes are odd, so //only mod with odd numbers //only need to go up to sqrt of num to find //out if it is prime for( int i = 3; i <= sr; i += 2 ) { /*test to see in num is prime */ if (num%i==0) { return false; } } return true;}

going only as far as the square root... I wouldn''t have thought of that Nice job!

~Vendayan

going only as far as the square root... I wouldn''t have thought of that Nice job!

~Vendayan

(Oh my God, is this really English?...)

I don''t know what it has to do with games , but ok:

There are some sites with a lot of info to this subject, but I found one way very intresting. It is called the sieve of Erasthadocalotheasth (or something like that

// create some space:
bool *isprime = (bool *)malloc(sizeof(bool) * 1000001);

// make true
for(int counter = 0; counter < 1000000; counter++)
isprime[counter] = true;

// The numbers are prime, until you can prove the oposite.


// begin with the first one (two), then sign every number
// that is dividable by that number with a false

for(int possible = 2; possible < 1000000; possible++)
{
if(isprime[possible])
{
for(int factor = 2; factor*possible <= 1000000; factor++)
{
isprime[factor*possible] = false;
} // for
} // if
} // for

// Now you''ve an array filled with which numbers are prime
// and which are not.

I hope that that will help...

Eratosthenes

Once there was a time when all people believed in God and the church ruled. This time is called the Dark Ages.

Thanks,

Those dead Greeks aren''t my best side, nice signature BTW!

You can speed it up a little more by recognizing that all primes after 2 and 3 are 6n+/-1 as well as being odd. Basically you just skip all multiples of two and three, i.e. 6n+/-2 is even and 6n+/-3 is divisible by three. That will enable you to check just two numbers out of six instead of three out of six.