**PROBLEM LINK:**

**Setter:** Anant Kumar

**Tester:** अनन्य शर्मा

**Editorialist:** Jatin Nagpal

**DIFFICULTY:**

EASY-MEDIUM

**PRE-REQUISITES:**

Binary Search, Sorting, Sieve of Eratosthenes, Binary Exponentiation

**PROBLEM:**

Given a number **N**, you have to tell the largest number \leq **N** such that it can be expressed in the form a^b, where a and b are prime numbers

**QUICK EXPLANATION:**

Store all possible a^b where **a** and **b** are prime, in an array(vector), sort the array(vector), and search for element \leq **N**

**EXPLANATION:**

- First Apply sieve for elements ranging from 2 to \sqrt{10^{11}}, as first prime is 2, and required max of a for a^b is \sqrt{10^{11}} and for b is log(10^{11})
- Create an array, for storing all a^b, apply nested loop for
**a**and**b**for all primes in increasing order, such that you break the inner loop when a^b exceeds 10^{11} - Sort the array
- Now Start reading test cases, for each test case, apply Binary Search in the array for largest element \leq
**N**

**Time Complexity:**

Let **D** be the number of elements in the range which is approx 3*10^4.

*O(\sqrt{N} log(log(\sqrt{N})) + T log(D) )*

**AUTHOR’S AND TESTER’S SOLUTIONS:**

Author’s solution can be found here

Tester’s solution can be found here