# Check If A Number Is A Prime Number

Problem:

Write a C++ program which checks if a number is a prime number or not?

A prime number is any natural number greater than 1 with no other positive factors other than 1 and itself.

Let's take 5 as an example:

1 and 5 (the number itself) can evenly divide 5 so they are factors of 5.The program below shows a number is asked and it is evaluated if a prime number or not.

2, 3, 4 are cannot evenly divide 5 so they are not factors of 5.

Therefore, 5 is a Prime Number.

Logic:

Let us start checking for its factors from 2 until the number itself. A factor is a number which can evenly divide the number thus it is checked if the remainder (modulus result) is 0. Every time a factor is seen, it is counted through a counter name countFactors.

When the loop ends, countFactors is checked.

If countFactors is equal to 1, meaning no other factor is found except for the number itself, it is a prime number. If countFactors is greater than 1, then it is not a prime number.

/* Prime Number Check if a number is a prime number or not. */ #include <iostream> using namespace std; int main(void) { //variables int number,i,countFactors; char hang; cout << "Enter the number: "; cin >> number; countFactors = 0; for (i = 2; i <= number; i++) { //if a factor exists from 2 up to the number, count Factors if (number % i == 0) { countFactors++; } } //a prime number has only itself as a factor other than 1 if (countFactors == 1) { cout << number << " is a Prime Number." <<endl; } else { cout << number << " is not a prime number but a composite number." << endl; } //to let console stay cin >> hang; return 0; }

Enter the number: 6 6 is not a prime number but a composite number.

If you want to have a logic to minimize the loop, you can check if the factor is lesser than the number. If the factor is lesser than the number, break the loop to minimize processing time. It will not continue checking for other factors because it is already found that there is other factor other than the number,thus it is not a prime number.

countFactors = 0; for (i = 2; i <= number; i++) { cout << i << ","; //if a factor exists from 2 up to the number, count Factors if (number % i == 0) { countFactors++; //break loop if a factor is lesser than the number if (i < number) { countFactors = 2; break; } } }

## 4 comments

Write commentsNice solution, but your one optimization does not do anything. i is of course smaller than number, that is what you check in your for loop. The first optimization step should be, that i only goes up until half of number, e. g. i <= (number/2). Because any i bigger than that would have to be multiplied by a factor smaller than 2 to get to number.

ReplyHi Patryk, thanks for you comment. I really appreciate it and will take a look at your solution and then share to others.

ReplyThanks a lot!

http://techcpp.blogspot.in/2016/04/program-to-check-whether-given-number.html

ReplyGet various ways to finds the prime numbers with new methods such as mathematical formula , c++ , c etc . You can also download materials to know more about prime numbers.

Reply