Help me out with my program

[Rajnish Kaushik]

i m trying to make a program for finding the number is prime or not in c++ with or without using fnctions

[Strange]

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

[Rajnish Kaushik]

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++?

[Sensei]

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

[Rajnish Kaushik]

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?

[Sensei]

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 );
}

[AtomicMaster]

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.

[Sensei]

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.

[AtomicMaster]

It was some years ago, i suppose it could have been algorithm-driven.