Question

Algorithem and flowchart to find a number is a prime or not?

Answer 1

To check a number wheteher it is prime or not we have to try and find its factors. If there are no factors of the number except 1 and the number itself we can call it prime.

But when we try to find factors we need a limit upto which we check for factors. The first thought is to check until the half of the number but upon critical thinking we can find that to check untill the square root of the number will be more efficient.

If we find no factors of the number except 1 until the square root of the number itself then we can safely say it's a prime number.

Below is the code for the function to check for prime

bool IsPrime(int number) { int root = sqrt(number) ; for(int i=2; i<=root; i++) { if(number%i == 0) return false; } return true;}

Notice that we start the loop with i=2, which skips the universal factor 1 and we go up until the square foot of the number. We check for the remainder of number divided by i and if it is zero we return false indicating the number isn't prime. If the loop runs until root and still doesn't find a factor we return true indicating the number is prime.