C++ Prime Numbers

[Victor89]

I don't know why it doesn't work correctly.
For example:
num=15, returns 1, and 15 isn't a prime number.

#include <iostream>
#include <conio.h>
using namespace std;

int PrimeNumber(int);

int main()
{
	int num;
	cout<<"num="; cin>>num;
	cout<<PrimeNumber(num);
	_getch();
}

int PrimeNumber(int num)
{
	for(int i=2;i<num; i++)
		if(num%i==0)
		{
			return 0;   //If it isn't a prime number
		}
		else
		{
			return 1; //If it is a prime number
		}

}

[xenovia12]

your program does not mean about finding prime numbers but checking if the num%i is equal to 0. :)

[Victor89]

I found the following solution which works perfectly.
What are your opinions on this? Is there an easier way to do it?

int PrimeNumber(int num)
{
	int count=0;
	for(int i=2;i<num; i++){
		if(num%i==0)
		{
			count++;   
		}
	}
		if (count==0)
		{
			return 1; //Returns 1 if the number is prime
		}
		else return 0;  //Returns 0 if the number is not prime

}

[AbstractionAnon]

lorence30 wrote:

your program does not mean about finding prime numbers but checking if the num%i is equal to 0. :)

And what do you think the definition of a prime number is?

Victor89 wrote:

num=15, returns 1, and 15 isn't a prime number.

The problem with your first algorithm is that you return unconditionally on the first iteration of the loop. i.e. The first time there is a remainder you return 1. There may be higher divisors that are evenly divisible. 15 / 2 returns 1.

Victor89 wrote:

What are your opinions on this? Is there an easier way to do it?

In your second algorithim, there is no reason to maintain a counter. The first time you find a number that is evenly divisible, then you should return immediately. The number is not prime and there is no need to check further divisors.

bool PrimeNumber (int num)
{   for(int i=2;i<num; i++)
    {    if (num%i==0)
            return false;  // Evenly divisible.  Not prime. No need to check further
    }
    return true;  // All possible divisors checked
}

An optimization of this algorithm is that you only need to check up to max_divisor, where max_divisor is sqrt(num).

[Ganado]

And what do you think the definition of a prime number is?

I think Lorence meant to say that his function only checks if num%2 == 0. But yeah you've explained it well.

[Victor89]

Thank you for your answers.

The only major difference is that i put an "else" in the code, and that else changes the entire result.

So the first time num%i==0 it should return false and stop, but it kept on going and that is why it returned true even if the number was prime. Is my understanding correct?

[AbstractionAnon]

i put an "else" in the code, and that else changes the entire result.

Correct.

but it kept on going and that is why it returned true

Because your loop started at 2, you were essentiall testing if num was even or odd. If even, you returned 0 which was correct. However, if num was odd, because of the else you immediately returned 1 indicating prime. You never got to testing divisors > 2.

[Victor89]

Thank you for your additional explanations.
Now I understand much better were my code was wrong.