Problem Solving :: Largest Prime from Toph

In this problem, task is to find out the largest prime number in a given range.
Statement says Q (1 ≤ Q ≤ 10^5), the number of queries that will be given. The next Q lines will contain two integers li (1 ≤ li) and ri (ri ≤ 10000).
So for solving this, I used a sieve algorithm for storing all the prime numbers is an array from 1 to 10000. Then I apply binary search for each query.

Comments

Post a Comment

Popular posts from this blog

Java notes Date:26/11/2019

#Like C++, when a function is static, run time polymorphism doesn't happen in Java. #Final methods cannot be overridden. #In Java, functions are virtual by default.  #Private methods are final and can not be overridden.   #It is compiler error to give more restrictive access to a derived class function which overrides a base class function. #A java array is always an object. #Arrays in Java are always allocated on heap.  
Read more

Problem Solving:: Be Like Hasib from Toph

Tag of this problem is binary search. Binary search problems seems very interesting to me.  Without thinking much about the problem I submitted a simple binary search algorithm. But got wrong answer 5 or 6 times. But after carefully reading the statement I understood I have to make change to my binary search algorithm. Modified Binary Search:: int count=0;     ll mid=-1;     while(l<h)     {         mid=(l+h)/2;         count++;         //cout<<l<<" "<<h<<" "<<mid<<endl;         if(x==mid)         {             h=mid;             continue;         }      ...
Read more