isPrime()

[forumposters]

I need to write a main() function, that loops over a bunch of
numbers from 0 to 100, calls another function called isPrime() for each of them, and print out the numbers that are prime.
I'm new to C++ and any help would be appreciated.

[Narue]

>I'm new to C++ and any help would be appreciated.
At least start trying to solve your problem before asking for help. It makes us like you more and ignore you less.

[sillyboy]

What narue said applies. But I'll help you a little: isPrime(int x)

[forumposters]

Here's what I've come up with so far:

#include <iostream>

  bool IsPrime(int num)
  {
 if(num == 0)
   return true;

 num = abs(num);

  for(int i = 2; i <= sqrt(num); i++)
   if(num % i == 0)
  return false;

  return true;
  }

[WaltP]

You've been around over a year and haven't read the Rules yet? You also need to read this . It will explain that you need to tell us what problem you are having so we don't have to guess -- among other things

[Narue]

>Here's what I've come up with so far
Somehow I find it hard to believe that you can write IsPrime but not the main driver to print the primes in the range [0..100). I'm guessing you were given IsPrime and told to write main, which means you've come up with nothing so far. But, the hard part is done already. All you need to do is loop from 0 to 100 and call IsPrime on the current number. If it returns true, print the number:

for ( int i = 0; i < 100; i++ ) {
  if ( IsPrime ( i ) )
    cout<< i <<" is prime\n";
}

[JRM]

>Here's what I've come up with so far Somehow I find it hard to believe that you can write IsPrime but not the main driver to print the primes in the range [0..100). I'm guessing you were given IsPrime and told to write main, which means you've come up with nothing so far. [/code]

LOL! If some people would put half of the effort that they put into "avoiding work" into something productive, they would have had the task acomplished by now!

If laziness is truely the mother of invention, we have quite a group of potential inventors here!

[soeja]

This is more efficient.

#include

bool IsPrime(int num)
{
if(num == 0)
return true;

num = abs(num);

if(num % 2 == 0) return true;

for(int i = 3; i <= sqrt(num); i+=2)
if(num % i == 0)
return false;

return true;
}

[soeja]

#include <iostream>

bool IsPrime(int num)
{
if(num == 0)
return true;

num = abs(num);

if(num % 2 == 0) return true;

for(int i = 3; i <= sqrt(num); i+=2)
if(num % i == 0)
return false;

return true;
}

[parameshyss]

Hi Soeja,
This is more efficient.. and for 4 , 6 , 8(i.e., even no) .. ur code snippet will give wrong ans..

#include <iostream>

bool IsPrime (int num)
{
if ( 2 == num ) return true ;
int l = sqrt(num) ;
for(int i = 3; i <= l; i+=2)
if ( 0 == ( num % i ) )
return false;

return true;
}

[hvengel]

An even more efficient and generalized isPrime() function.

bool isPrime (unsigned int number)
{
    if (number > 3) {
        if (number % 2 == 0) return false;
        
        const unsigned int MAX = (unsigned int)sqrt(number) + 1;
        for (unsigned int i = 3; i < MAX; i += 2 )
            if ( (number % i) == 0)
                return false;
              
        return true;
    }            
    
    if (number < 2) return false;
    
    return true;    
}

[parameshyss]

Gud work hvengel.. :)

[StuXYZ]

I am surprised reading this, I would have thought most of you knew the +2,+4 rule --
but it hasn't come up, just the old +2 rule.

Assuming that you are not going to use the memory that the typical sieve methods use, or the complexity of the more you can extend the idea that you increment the test by +2 to +2,+4 as below.

bool isPrime2(unsigned int& number)
{
  if (number > 3) 
    {
      if (number % 2 == 0) return false;
      if (number % 3 == 0) return false;
      const int MAX = (int)sqrt(number) + 1;
      int i=5;
      while(i<MAX)
	{
	  if ( (number % i) == 0) return false;
	  i+=2;
	  if ( (number % i) == 0) return false;
	  i+=4;
	}
    }
  else if (number<2) 
    {
      return false;
    }
  return true;    
}

The code as given is about 45% quicker than the simple +2 system. However, there are many other ways of doing things.

The next obvious extension is sometimes called the wheel factorization , e.g. http://primes.utm.edu/ That reference has lots of other algorithms as well.

[pseudorandom21]

I think a sieve that uses a bit of memory is way better than using that much CPU time, you can generate millions of primes in a few seconds using a sieve.

[hvengel]

#include <math.h>
#include <vector>

using namespace std;

const int NUM_FIRST_PRIMES = 3;
const unsigned int FIRST_PRIMES[NUM_FIRST_PRIMES] = {2, 3, 5};

vector<unsigned int> sieve;   
unsigned int wheelFactor = 1;
bool seiveFull = false;
    
void fillSieve() {
    
    wheelFactor = 1;

    for (int i=0; i < NUM_FIRST_PRIMES; i++)
    wheelFactor = wheelFactor * FIRST_PRIMES[i];    
        
    unsigned int i = 0;
    int sieveValue = FIRST_PRIMES[NUM_FIRST_PRIMES - 1] + 1;
    while (sieveValue < wheelFactor){
        bool factor = true;
        for (int j=0; j < 8; j++)
            if (sieveValue % FIRST_PRIMES[j] == 0) { 
                i++; 
                factor = false;
                break;                
            }
        if (factor) { 
            sieve.push_back(sieveValue); 
            
           } 
        sieveValue++;
        
    }
    sieve.push_back(wheelFactor + 1);
    sieveFull = true;
}
 

bool isPrime (unsigned int candidatePrime)
{  
    if (!sieveFull) fillSieve();
    
    int fp = 0;
    while (fp < NUM_FIRST_PRIMES) {
        if (candidatePrime == FIRST_PRIMES[fp]) return true;
        if (candidatePrime % FIRST_PRIMES[fp] == 0 && candidatePrime > 3) return false;
        fp++;
    }
    
    const unsigned int MAX = (unsigned int)sqrt(candidatePrime);
    int pass = 0;
    while (pass < MAX) {
        int i = 0;
        while (i < sieve.size())  {
            if (candidatePrime == (pass + sieve[i])) return true;
            if (candidatePrime % (pass + sieve[i]) == 0) return false;
            i++;
        }  
        pass += wheelFactor;
    }
    
    return true;
}

Here is a wheel factorization version of isPrime. This uses a small wheel factoring sieve based on the first three primes. When used to find the sum of all primes up to some limit it is slower than my earlier function up to finding the sum of all primes below 100,000 and faster for larger test cases. It is about 40% faster when finding all primes below 1,000,000 and about 45% faster when finding the first 20,000,000 primes. This is probably because of the extra overhead of building the sieve and perhaps some added overhead from using a vector to hold the sieve.

It should be possible to extent this to use a larger sieve by using a larger first primes set and this should make it run faster when testing larger values or when working with a larger set of data but it will be even slower when using it with smaller data sets because of the added initialization overhead which grow exponentially as the number of first primes get bigger.

I have not tested this code with a bigger sieve so it might needs some tweaks.

[pseudorandom21]

http://en.wikipedia.org/wiki/Primality_test

You might also look into the sieve of eratosthenes, and other algorithms for generating primes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

There are links to other algorithms at the bottom, such as the sieve of sundaram, etc.

[yashsaxena]

prime number program :)
Still remember the initial days of C & CPP programming Language. :P :)