How to check for prime number

[kalp1200]

Hi

I am doing this exercise from a book, and I need to be able to identify a prime number. According to the rules, a number is prime number if its odd and the prime number should be divisable with any numbers less or equal to the square root.

I have done the following so far, I hope someone can point out what's wrong here, at times i get 2 statements in the output and sometimes..I get the correct output and sometimes, the program hangs..if I enter the number as 5.

/*q7*/

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
	int positive_integer,number,positive_integer_new,answer;
	double division;
	bool prime;



	cout<<"Enter a positive integer"<<"\n";
	cin>>positive_integer;

	if(positive_integer==2)
	{
		cout<<"This is a prime number"<<"\n";
	}
	else if(positive_integer%2==0)
	{
		cout<<"This is a NOT a prime number, it is divisible by 2 and is even"<<"\n";
	}
	else if(positive_integer%2!=0)
	{
		number=static_cast<int>(pow(positive_integer,0.5));
		positive_integer_new=positive_integer;

		cout<<"The numbers equal and less than the square root is "<<number<<" "<<"\n";
		cout<<"Positive integer "<<positive_integer_new<<" divide "<<number<<" is "<<positive_integer_new/number<<" and the remainder is "<<positive_integer_new%number<<"\n";

		while(positive_integer_new%number!=0)
		{
			
				number=number-2;
				answer=positive_integer_new%number;
				division=positive_integer_new/number;
				if(number!=1)
				{
					cout<<"Positive integer "<<positive_integer_new<<" divide "<<number<<" is "<<division<<" and the remainder is "<<answer<<"\n";

					if(answer!=0)
					{
						prime=true;
					}
					else if(answer==0)
					{
						prime=false;
					}	
				}
			
			
		}
	}

	if(prime=true)
			cout<<"This is a prime number"<<"\n";
	else
		cout<<"This is NOT a prime number"<<"\n";

	return 0;
}

[hamsterman]

your problem is the while loop. while(positive_integer_new%number!=0) means that it will loop forever if positive_integer_new is prime. lines 38-40 will cause your program to crash if number is even. A simple algorithm to test if a number is prime could look like this:

bool is_prime(int positive_integer){
    for(int number = sqrt(positive_integer); number > 1; number--){
        if(positive_integer % number == 0) return false;
    }
    return true;
}

The idea is to take every number smaller or equal to the root of positive_integer and see if positive_integer can be divided by it. Of course this could be optimized, but I'll leave that to you.