Jump to content

Help me out with my program


Rajnish Kaushik

Recommended Posts

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

Link to comment
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?

Link to comment
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 );
}

Link to comment
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.

Link to comment
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.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.