Mathophobia Problem Code: MATPH

help
1

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;
}
2

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.