To Find Number Is Prime Or Not At Very Less Complexity (O(sqrt(n)))

Prime numbers are the numbers which has only 2 factors i.e divisble by 1 and the number itself


Function:

bool isPrime(int n)
{
if(n<=1)   // if number is less than  number is not prime
  return false;
if(n<=2)     // if number is less than 2 than it prime because it is divisible by 2 and 1
  return true;
if(n%2==0||n%3==0)   // if the number is divided by 2 or 3 than it is not prime
{
return false;
}
for(int i=5;i*i<=n;i=i+6) 
     // check for 5 and than 11 than 17 which is all prime number  
   {
    if(n%i==0||n%(i+2)==0) 
   // check for 5 than 7 than 11 than 13 and so on
       return false;
   }
return true;
}

Twisted Prime Number

A Twisted Prime is a number whose itself is a prime number and its reverse is also prime number .


To solve this problem following are the approaches should be taken:

1)Check the number is prime or not 
2) If YES the REVERSE it and check  whether the number is Prime or not.


Programme:

//TO CHECK NUMBER IS PRIME  OR NOT AT   TIMECOMPLEXITYO(SQRT(n))  isPrime()
#include<bits/stdc++.h>
using namespace std;
bool isPrime(int n)     
           
{
if(n<=1)
  return false;
if(n<=2)
  return true;
if(n%2==0||n%3==0)
{
return false;
}
for(int i=5;i*i<=n;i=i+6)
   {
    if(n%i==0||n%(i+2)==0)
       return false;
   }
return true;
}

int revresee(int n)
{
int sum=0;
while(n>0)
{
int c=n%10;
sum=sum*10+c;
n=n/10;

}
return sum;
}




main()
{
int t;
cin>>t;
while(t>0)
{
int n,c;
cin>>n;
if(isPrime(n))
{
c=revresee(n);
//cout<<c;
if(isPrime(c))
  {
  cout<<"Yes"<<"\n";
  }
  else
    cout<<"No"<<"\n";
}
else
  cout<<"No"<<"\n";
}

}




For PRACTICE this question check this link:
  https://practice.geeksforgeeks.org/problems/twisted-prime-number/0 

Find four elements that sum to a given value

THESE IS THE QUESTION ASKED IN AMAZON AND OYO ROOMS

THE QUESTION IS TO

FIND ALL THE POSSIBLE CASE WHOSE SUM SHOULD BE THE SUM OF FOUR ELEMENTS IN THE ARRAY.

INPUT
 8
 10 2 3 4 5 9 7 8
 23

OUTPUT
  3  5 7 8   (3+5+7+8=23)


For Understanding These Question:

  https://www.geeksforgeeks.org/find-four-numbers-with-sum-equal-to-given-sum/

For Practicing :

 https://practice.geeksforgeeks.org/problems/four-elements/0



PROGRAMME:





#include<bits/stdc++.h>
using namespace std;



void throughnaivesolution(int a[],int n,int X)     //time complexity O(n^4)
{
for(int i=0;i<n-3;i++)
   {
    for(int j=i+1;j<n-2;j++)
    {
    for(int k=j+1;k<n-1;k++)
    {
    for(int l=k+1;l<n;l++)
    {
    if(a[i]+a[j]+a[k]+a[l]==X)
      cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[l]<<"\n";
   
    }
    }
    }
   }
}


void throughsorting(int a[],int n,int X)   //O(n^3)
{
sort(a,a+n);
for(int i=0;i<n-3;i++)  //n
{
for(int j=i+1;j<n-2;j++)   //n
{
int k=j+1;
int l=n-1;
while(k<l)     //n
{
if(a[i]+a[j]+a[k]+a[l]==X)
  {
  cout<<a[i]<<" "<<a[j]<<" "<<a[k]<<" "<<a[l]<<"\n";
  k++;
  l--;
  }
  else if(a[i]+a[j]+a[k]+a[l]<X)
  {
  k++;
  }
  else
   l--;
}
}
}
}



main()
{
   int t;
   cin>>t;        // NUMBER OF TEST CASES
   while(t--)
   {
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
      cin>>a[i];
   
int X;
cin>>X;

throughnaivesolution(a,n,X);

cout<<"\n\n\n";

throughsorting(a,n,X);
 
     
   
     
     
     
   }
}