#### Archived

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

# Finding primes less than 1 mill?

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

## 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 on other sites
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.

  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 on other sites
going only as far as the square root... I wouldn''t have thought of that Nice job!

~Vendayan

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

~Vendayan

##### 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 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 on other sites
Thanks,

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

##### 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 9
• 11
• 11
• ### Forum Statistics

• Total Topics
633679
• Total Posts
3013300
×