# Mathophobia Problem Code: MATPH

Question: Mathophobia
I don’t understand why it is giving WA for first two cases. Can somebody explain the flaw in the logic? Also if possible, I’d like an explanation for why is it TLE-ing?

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

void sieve (long long limit, set <long long> &prime) {
vector <bool> mark (limit+1, true);

for (long long i=2; i*i<mark.size(); i++) {
if (mark[i]==true) {
for (long long j=i*2; j<mark.size(); j+=i)
mark[j]=false;
}
}

for (long long i=2; i<mark.size(); i++) {
if (mark[i]==true) {
prime.insert(i);
}
}
}

int main() {
int T;
cin>>T;

while (T--) {
long long N;
cin>>N;

set <long long> prime;
sieve(N, prime);

long long ans=-1;

for (auto it=prime.begin(); it!=prime.end(); it++) {

long long a = log (N)/log(*it);
if (prime.find(a)==prime.end())
continue;

ans = max(ans, (long long)(pow((*it), a)));
}

cout<<ans<<endl;
}
return 0;
}``````

Few Suggestions:

• You can insert in the prime set inside the loop itself, no need to have an additional loop at the end of the sieve function.
• Avoid using Logarithms. Always try to solve such problems in integers at first.
• See other people’s solutions. Don’t do this often, as this takes all the fun out of Problem Solving.