Primality C++ Test Using a Basic Concept of Number Theory

-

 Primality testing is some sort of exciting stuff for a beginner in coding. There are various techniques for doing this. Following code is written by me that used the following fact that -: "N is a composite number if it has at least one non-trivial divisor d, such that d is less than or equal to sqrt(N)". 

Proof of the fact is simple and can be proved using contradiction(Hint -; N is composite. What if all the non-trivial divisors are greater than sqrt(N)? ).

Direct link -: http://cpp.sh/7sng3

// To detect whether a number is prime or not.

// Written by Sushant

#include <iostream>

#include<cmath>

using namespace std;


int main()

{

int p,q,i(0),d(0);

cout<<"Enter the number -: \n";

cin>>p; // enter the prime


q=int(sqrt(p)); // storing the integer part of square root


                  for(i=2; i <= q;i++)

                           {

                                // using the fact that if x is a composite number then it must have a non-trivial divisor less than or equal to sqrt(x)

                                

                                if (p%i == 0) 

                                        {

                                            d++;

                                            i=q+1; // to stop the for loop

                                        }

                            }

                            

                            // Now the final result


                  if(d==0)

                           { 

                               if(p==1)

                                    cout<<"is not prime";

                               else

                                    cout<<"is prime";

                           }

                  else

                            cout<<"is not prime";


 return 0;

  

}

Comments

Post a Comment

Popular posts from this blog

Compactness in Metric Spaces

-
Image
  The idea of compactness comes from the fact that these are the nice set next to the finite sets. i.e. It shares many properties of finite sets in a topological space. The first thing common between finite and compact sets is, these are closed and bounded. Every sequence has a limit point. A continuous image of a compact set is compact and many more. Compactness has a very close relation to completeness . Let X be a topological space then the definition of compactness is defined in the following way-: X is said to be compact if every open covering of X has a finite sub-covering. Heine-Borel Theorem -: Heine-Borel make our work easy for Euclidean spaces by generalizing that, ‘ K is a compact subset of R if and only if it is closed and bounded. ’ But above theorem doesn’t work well for all metric spaces , for example -: Take N with discrete metric. What is missing here? Completeness? No! Boundedness? No! Closedness? No! Then what? The thing that is missing is totally bounded
Read more

Hilbert's Irreduicibility Theorem

-
Hilbert's Irreduicibility Theorem :  Let $\Q$ be the field of rational numbers and $f_1(x_1, x_2, ..., x_n, y_1, y_2, ..., y_m), f_1(x_1, x_2, ..., x_n, y_1, y_2, ..., y_m),...,f_r(x_1, x_2, ..., x_n, y_1, y_2, ..., y_m)$ be a set of irreducible polynomials in $\Q(x_1, x_2, ..., x_n)[y_1, y_2, ..., y_m]$ . Then Hilbert's Irreduicibility Theorem tells that there exists an n-tuple $(a_1, a_2, ..., a_n)$ in $\Q^n$ such that $f_1(a_1, a_2, ..., a_n, y_1, y_2, ..., y_m), f_2(a_1, a_2, ..., a_n, y_1, y_2, ..., y_m),..., f_r (a_1, a_2, ..., a_n, y_1, y_2, ..., y_m)$ are irreducible in $\Q[ y_1, y_2, ..., y_m]$. A cute application of above theorem is that, If a polynomial $p(x)$ in $\Q[x]$ takes square value at every points in $\Q$ then $p(x)$ is itself a square in $\Q[x]$. (Hint : Apply Hilbert's irreducibilty to f(x, y) = y^2-g(x).)
Read more