1
#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?

Divanshu Garg
  • 19
  • 3
  • 5
    You have other difference than just `sqrt`, you break unconditionally. – Jarod42 Nov 26 '21 at 13:11
  • Plural of code isn't codes. – user438383 Nov 26 '21 at 13:12
  • 2
    If a number, n, divides by something greater than sqrt(n) then result will be lower than sqrt(n), a value you'll already have tested. Second version makes use of that fact. – 500 - Internal Server Error Nov 26 '21 at 13:13
  • Factors come in pairs. Now consider `a * b = c` and what is the biggest possible value of `min( a,b)` – 463035818_is_not_an_ai Nov 26 '21 at 13:16
  • it is all about efficiency and time, the faster and efficient one is always preferred – Abhilekh Gautam Nov 26 '21 at 13:16
  • 3
    There are other differences than efficiency. For example, yours doesn't work; according to that, all odd numbers are prime numbers. You also ignore the smallest prime number, 2. – molbdnilo Nov 26 '21 at 13:16
  • Think some more about how many iterations your loop is doing. In what conditions *doesn't* it break out of the loop? – molbdnilo Nov 26 '21 at 13:25
  • @user438383: Please feel empowered to make edits to a question. Note also that non-native speakers of English are most welcome on this site, and the tone of your comment does not help that. – Bathsheba Nov 26 '21 at 14:02
  • @Bathsheba I did make an edit. And I know non native speakers almost always prefer to be corrected when they make mistakes in English or else they don't learn how to correct their mistakes. – user438383 Nov 26 '21 at 14:16
  • 1
    @user438383: "Plural of code isn't codes." is not polite English. Consider removing your first comment before the moderators do. – Bathsheba Nov 26 '21 at 14:24

2 Answers2

2

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.

Jarod42
  • 203,559
  • 14
  • 181
  • 302
Yash Sonalia
  • 378
  • 2
  • 8
0

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 and i is implicitly converted to a double in the evaluation of the expression. 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).

Bathsheba
  • 231,907
  • 34
  • 361
  • 483