#include <iostream>
#include<cmath>
using namespace std;

int main()
{
   int n;
   cout << "Enter the no. and we will tell you whether it's Prime or Non-Prime \n";
   cin >> n;
   
   for (int i=2; i<n; i  ) {
       if (n%i== 0){
           cout << "Non-Prime"<< endl;
           break;
       }
       else {
           cout << "Prime" << endl;
       } break;
   }

    return 0;
}

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
   int n;
   cout << "Enter the no. and we will tell you whether it's Prime or Non-Prime \n";
   cin >> n;
   
   bool flag=0;
   
   for (int i=2; i<=sqrt(n); i  ) {
       if (n%i== 0){
           cout << "Non-Prime"<< endl;
           flag=1;
           break;
       }
   }
         if (flag ==0) {
           cout << "Prime" << endl;
       }

I wrote two pieces of code, simpler one is mine but the other second one having square root function involved was from internet. I want to program a simple code telling me whether a number is prime or not, so please tell me though both pieces of code do the same work what is logic in the second code and is it really necessary to write it in that way?

CodePudding user response：

Mathematically, if a factor is greater than the square root of a number n, the other factor that would multiply with it to equal n is necessarily less than the square root of n.

Here,

Since sqrt(n) <= n, it saves a lot of computation time when n is a large number.

Check this answer.

CodePudding user response：

You only need to go up to and including the square root of the number, since once you've pulled out a lower factor, the higher one drops out too.

Note that

i <= n / i

is a better way of specifying the stopping conditional: a std::sqrt takes a few clock cycles to evaluate. Only IEEE754 guarantees the result is the best it can be for an output double, standard C does not. Writing i * i <= n is also tempting but that can cause i to overflow with undefined results.

Writing i = 2 as the increment also yields a small gain, albeit at the expense of the purity of the approach (the function should be telling you that even numbers are not prime, not you telling it; in full generality you only need to iterate over the prime numbers up to and including the square root of n).