#include <iostream>
      #include <math.h>
      using namespace std;
      int main()
      {
          int i,n = 29;
          bool isprime= true;
          // 0 and 1 are not prime numbers also, negative numbers are not prime
          if(n < 2)
          {
              isprime = false;
          }
          else
          {
          // If a number n is not a prime, it can be factored into two factors a and b:
          // n = a * b
          /*Now a and b can't be both greater than the square root of n, 
          since then the product a * b would be greater than sqrt(n) * sqrt(n) = n.
          So in any factorization of n, at least one of the factors must be smaller 
          than the square root of n, and if we can't find any factors less than or equal to 
          the square root, n must be a prime.*/
              for(i=2; i < sqrt(n); i++)
              {
                  if(n % i == 0)
                  {
                      isprime = false;
                      break;
                  }
              }
          }
          string result = isprime ? "Prime":"not Prime";
          cout<<"The number " << n << " is : " << result;
          return 0;
      }
      
      Cpp language logo

      Korta

      0

      0

      avatar
      Yatharth Garg

      0 Comments

        Add Comment

        Log in to add a comment

        Codiga - All rights reserved 2022.