Primality_Test.cpp

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==2 || n==3) cout<<"Prime Number";
    else if(n<=1 || n%2==0 || n%3==0) cout<<"No Prime";
    else 
    {
        for(int i=5;i<=sqrt(n);i+=6)
        {
            if(n%i==0 || n%(i+2)==0)
            {
                cout<<"NO Prime Number";
                return 0;
            }
        }
        cout<<"Prime Number";
    }
}
//Another approach: It is based on the fact that all primes greater than 3 are of the form 6k ± 1, 
//where k is any integer greater than 0. This is because all integers can be expressed as (6k + i), 
//where i = −1, 0, 1, 2, 3, or 4. And note that 2 divides (6k + 0), (6k + 2), and (6k + 4) and 3 divides (6k + 3). 
//So, a more efficient method is to test whether n is divisible by 2 or 3, then to check through all numbers of the form 6k ± 1 <=.Vn 
//This is 3 times faster than testing all numbers up to √n.