Calculation Help - Prime Numbers

[Takafoo]

Hey,

Ive got a program I'm try to work on that the user enters the number and then it reports back if the number is prime or not. So far my calculations are completely off and I have no idea how to fix them or what they should be. Any help would be great.

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int);
int getNumber();

int main()
{
   int number = getNumber();

   if (isPrime(number)) 
      cout << "\n" << number << "is a prime number\n";
   else 
      cout << "\n" << number << "is not a prime number\n";

   return 0;
}

int getNumber()
{
   int number;
   cout << "Please enter a positive number ";
   cin >> number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
   return number;
}

bool isPrime(int number)
{
   int count, s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number % 2 == 0) return true;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=1; count<=s; count+=2);
   {
      if (number % count == 0)
      isprime = false;
   }
   return false;
}

[vmanes]

Why does your isPrime( ) function return true when the number is divisible by 2, and returns false in every, repeat EVERY, other case? Look at it closely.

[Takafoo]

I don't really understand the concept of a prime number or how to calculate it sorry.

[monkey_king]

I don't really understand the concept of a prime number or how to calculate it sorry.

Then you should ask in a mathforum and not a c++ programmer forum.

A prime number is a number that only has 2 divisors.
the number one and the number itself.

This means that if you can find a number: not 1 and not the number itself, that divides you original number (no remainder).

Then it's not a prime number.
edit:
So your loop shouldn't start at 1 but at 3.

[Takafoo]

Ok so should it be similar to below?

bool isPrime(int number)
{
   int count, s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number == 2) return true;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0)
      isprime = false;
   }
   return true;
}

[Akhilleus]

That's better, but it still isn't going to work.

1) You use the variable "bool isprime", but you never return it. That means that if in your for loop you find out a number isn't prime, and you set isprime = false... When the for loop ends you return true anyway. What you want is either to return false (which will also end the function when called) in place of changing the value of isprime, or to return isprime instead of true at the end of the function, after the for loop.

Note: If you do the second option, your for loop is going to continue searching pointlessly even once you've already determined that number isn't prime and set isprime = false. You're going to want to put a check on that, probably, to avoid wasting time going through all the other numbers. Once you know number is not prime, you don't need to check anymore, so why continue the for loop for all those numbers all the way up to sqrt(number)?

2) If number == 2 (prime) you return true. That's correct. Then later on (once you fix it) you check whether a number is divisible by any odd number less than its square root and decide whether it's prime based on that. That's also correct. But you still aren't checking for even numbers (evenly DIVISIBLE by two), like your comment your check for equality with 2 says. Two is prime, but all other even numbers are not.

[Takafoo]

Thanks for your help. I know I'm painful sorry about that. So i change it to return isprime instead of true at the end right? And that will break the loop out.

Then "if (number % 2 == 0) return false;" should see if when divided by 2 it doesnt a remainder it sets to false, right?

bool isPrime(int number)
{
   int count, s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number == 2) return true;

   if (number % 2 == 0) return false;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0)
      isprime = false;
   }
   return isprime;
}

[siddhant3s]

Takafoo, groom your basics. You don't even know how to use the modulo operator %.
Now lets work upon how to guess if number is prime or not.
What we gonna do is take the number and find its remainder when divided by numbers from 2 till the number-1.
For say, if the input number is 33 we gonna check if the number is divisible by
2? 3? 4? 5?........... 31? 32?
If all the answers are NO, then the number is prime. If even one of the answer is YES, the number is not a prime.
So, how do we do that?
We construct a for-loop from 2 to the number-1:

for(int i=2; i < n ; i++)
{
//body of loop
}

Now, inside the body, we will check if the number, n is divisible by each i by using the modulo operator:

for(int i=2; i < n ; i++)
{
if (n%i==0)
return 0;//indicating it is not a prime
}
return 1;//after the loop pass all the test, we are confirmed that
              //the number is prime, so return 1 for success

so the whole thing will look something like this :

int isPrime(int n)
{
  for(int i=2; i < n ; i++)
     {
       if (n%i==0)
            return 0;//indicating it is not a prime
     }
   return 1;//after the loop pass all the test, we are confirmed that
              //the number is prime, so return 1 for success
}

Note that however, it is well established in mathematics that if a number say n passes the test till squareroot of n than we can confirm that the number is a prime number.
Considering this, the code will look like this:

int isPrime(int n)
{
  for(int i=2; i <= sqrt(n) ; i++) //sqrt requires you to #include< cmath>
     {
       if (n%i==0)
            return 0;//indicating it is not a prime
     }
   return 1;//after the loop pass all the test, we are confirmed that
              //the number is prime, so return 1 for success
}

You should perhaps read the whole thing here and try to re-invoke the whole thought process yourself. And then try to write the program yourself(rather that doing a copy-paste)

[Takafoo]

I'm sorry I don't know what is wrong with the modulus statement I wrote? It compiles as it is now. I just get the below error:

g++ -lm prime.cpp
prime.cpp: In function 'void getNumber(int&)':
prime.cpp:26: error: invalid type argument of 'unary *'

I know if I take the *number to number it will work but I've been told I have to have a pointer in the getNumber function but I don't know how else to do it.

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int);
void getNumber(int &number);

int main()
{
   int number;

   getNumber(number);

   if (isPrime(number)) 
      cout << "\n" << number << "is a prime number\n";
   else 
      cout << "\n" << number << "is not a prime number\n";

   return 0;
}

void getNumber(int &number)
{
   cout << "Please enter a positive number ";
   cin >> *number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
}

bool isPrime(int number)
{
   int count;
   double s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number == 2) return true;
   if (number % 2 == 0) return false;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0) 
      return false;
   }
   return isprime;
}

[VernonDozier]

I know if I take the *number to number it will work but I've been told I have to have a pointer in the getNumber function but I don't know how else to do it.

Been told by who, and why do you have to have a pointer? Is it part of the program specification so that you can prove that you know how to use pointers? If not, I don't see why the program couldn't be written without pointers. If you have to have a pointer in the getNumber function you can change the function spec to this:

void getNumber(int *number)

and keep the same implementation code. You'd have to change the function call in main to make it compatible though.

[Takafoo]

It's part of the specification. So change as below?

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int);
void getNumber(int &number);

int main()
{
   int number;

   getNumber(&number);

   if (isPrime(number)) 
      cout << "\n" << number << "is a prime number\n";
   else 
      cout << "\n" << number << "is not a prime number\n";

   return 0;
}

void getNumber(int *number)
{
   cout << "Please enter a positive number ";
   cin >> &number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
}

bool isPrime(int number)
{
   int count;
   double s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number == 2) return true;
   if (number % 2 == 0) return false;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0) 
      return false;
   }
   return isprime;
}

[VernonDozier]

You can keep the function implementation BODY the same as before and change the function spec, it seems to me, so:

void getNumber(int *number)
{
   cout << "Please enter a positive number ";
   cin >> *number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
}

Change the function declaration at the top to match, then start changing things in main (i.e. function call and the type of number) so everything matches. If you don't understand pointers and the * and & operators and how to use them, read up on them because otherwise it isn't going to make any sense regarding what you need to change (you don't have to change all that much). but I imagine that the function itself is supposed to be what I have above, which is what you had before, except for a single change from a & to a *.

However, if you were given a spec, make sure everything conforms to it. I am assuming the above is what is expected, but not having seen it, it's just an assumption.

[Takafoo]

Ok changing the main() to something like:

void getNumber(int *number);

int main()
{
   int *number;

   getNumber(*number);

   if (isPrime(number))
      cout << "\n" << number << "is a prime number\n";
   else
      cout << "\n" << number << "is not a prime number\n";

   return 0;
}

But isn't that going to stuff the call in isPrime?

[VernonDozier]

Ok changing the main() to something like:

void getNumber(int *number);

int main()
{
   int *number;

   getNumber(*number);

   if (isPrime(number))
      cout << "\n" << number << "is a prime number\n";
   else
      cout << "\n" << number << "is not a prime number\n";

   return 0;
}

But isn't that going to stuff the call in isPrime?

Yep. That means you'll have to change the either the isPrime function or the call to isPrime. Change something, recompile, see if you get farther than before. Keep changing things in an organized fashion till it all works. It's a step-by-step process and you'll definitely make lots of mistakes before getting it right. In your case there isn't much to change

[Takafoo]

Ok playing around I think I've sorted it out. Thanks for your help.

Last question though. Can someone double check the isPrime function for logic errors for me?

I was just playing with it and it looks like it still reads 33 as being prime but I'm not sure why, I've tried desk checking it but I can't work it out. I think it is because of the count<=s statement but I'm not sure what I should change it too to make it work.

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(int &number);
void getNumber(int* const number);

int main()
{
   int number;

   getNumber(&number);

   if (isPrime(number)) 
      cout << "\n" << number << " is a prime number\n";
   else 
      cout << "\n" << number << " is not a prime number\n";

   return 0;
}

void getNumber(int* const number)
{
   cout << "Please enter a positive number ";
   cin >> *number;
   if (!cin.good())
   {
      printf("Invalid number entered\n");
      exit(1);
   }
}

bool isPrime(int &number)
{
   int count;
   double s;
   bool isprime = true;

   /* Every even number is not prime */
   if (number == 2) return true;
   if (number % 2 == 0) return false;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0) 
      return false;
   }
   return isprime;
}

[vmanes]

Logic looks OK, a couple suggestions.

bool isPrime(int &number)
{
   int count;
   double s;
   //bool isprime = true; //delete, you return true/false directly

   /* Every even number     except 2     is not prime */
   if (number == 2) return true;
   if (number % 2 == 0) return false;

   /* check every odd number up to the square root of the number */
   s = sqrt(number);
   for (count=3; count<=s; count+=2);
   {
      if (number % count == 0) 
      return false;
   }
   //return isprime;   //delete this, just return value 
   return true;
}

Since you never store anything else to isprime, you directly return true and false within the code body, why bother even having it?