## Recommended Posts

Apart from just trying to divide the number by every smaller value (which will work but is very, very inefficient), this is about the simplest (and oldest) prime test: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

##### Share on other sites

Apart from just trying to divide the number by every smaller value (which will work but is very, very inefficient), this is about the simplest (and oldest) prime test: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

that was great but how can i use that in c++?

##### Share on other sites

If we will be writing code for you, you won't learn anything..

The simplest prime search code (copy'n'pasted from mine own application):

bool IsPrime1( unsigned long long value )
{
if( value < 2 ) return( false );
unsigned long long max = (unsigned long long) sqrt( (double) value );
for( unsigned long long i = 2; i <= max; i++ )
{
if( ( value % i ) == 0 )
{
return( false );
}
}
return( true );
}

It will work with primes smaller than 4,294,967,296

##### Share on other sites

If we will be writing code for you, you won't learn anything..

The simplest prime search code (copy'n'pasted from mine own application):

bool IsPrime1( unsigned long long value )

{

if( value < 2 ) return( false );

unsigned long long max = (unsigned long long) sqrt( (double) value );

for( unsigned long long i = 2; i <= max; i++ )

{

if( ( value % i ) == 0 )

{

return( false );

}

}

return( true );

}

It will work with primes smaller than 4,294,967,296

my c++ knowledge is not of that high level is there something easier?

##### Share on other sites

It's the simplest possible code for range between 2 and 4 billions primes.

You could degrade range to 2...65536 by replacing "unsigned long long" by "int".

And degrading speed by removing sqrt() line.

But I see no sense in this action.

bool IsPrime1( int value )
{
if( value < 2 ) return( false );
for( int i = 2; i < value; i++ )
{
if( ( value % i ) == 0 )
{
return( false );
}
}
return( true );
}

##### Share on other sites

I recall working on this back in 2009(ish)

If you want a speedy algorithm for checking a large amount of numbers for primity;

bool is_prime(int num)
{

//lets see we need to check for a couple of things first

//compare to single digit primes, why? they are the only ones with irregularities
if (num < 8)
{
static bool firstPrimes[] = {false, false, true, true, false, true, false, true};
return firstPrimes[num];
}

//now lett's check for simple division, this weeds out a LOT of numbers
if (num%2==0 || num%3==0 || num%5==0 || num%7==0)
{
return false;
}

//exploiting what we know about the prime set, weed out even MORE numbers
if((num+1)%6==0 || (num-1)%6==0)
{
//unfortunately we still need to do this, this is the only way to check if the number has prime factors...
int to = sqrt(num+1);
for(int i=2; (6*i)-1<=to; i++)
{
if(num%((6*i)+1)==0 || num%((6*i)-1)==0)
{
return false;
}
}
return true;
}
return false;
}

Sensei, if i recall you should do value+1 to eliminate some false-positives due to casting.

Raj, that C++ is very basic, so basic that reading 10-12 pages into a C++ manual/text book should give you all the knowledge to understand everything there except for type-casting.

##### Share on other sites

Sensei, if i recall you should do value+1 to eliminate some false-positives due to casting.

But you're doing slightly different algorithm than me in post #4.

Any example value that is causing it?

I scanned the all first 1,000,000 numbers using two different algorithms and found 78,498 primes. Exactly the number we should get.

## Create an account

Register a new account