• Advertisement

Archived

This topic is now archived and is closed to further replies.

Finding primes less than 1 mill?

This topic is 5827 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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!

Share this post


Link to post
Share on other sites
Advertisement
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;

}

Share this post


Link to post
Share on other sites
going only as far as the square root... I wouldn''t have thought of that Nice job!

~Vendayan

Share this post


Link to post
Share on other sites
going only as far as the square root... I wouldn''t have thought of that Nice job!

~Vendayan

Share this post


Link to post
Share on other sites
(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...

Share this post


Link to post
Share on other sites
Eratosthenes

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement