How is this code getting accepted?

help
, ,
1

MRTRAVEL
Please have a look at the question.
Please have a look at this code snippet. It is not long. Thanks for your patience.

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
        int n; 
        cin>>n; 
        vector<int> a(n); 
        for(int i=0;i<n;i++) cin>>a[i];
        sort(a.begin(),a.end()); // sorting the elements of array
        int ans=0;
        map<int,bool> mpx;  // to keep track of elements who are already placed in group
        for(int i=0;i<n;i++) {
              if(!mpx[a[i]]){
                   ans++;
                   for(int j=i+1;j<n;j++){
                        if(a[j]%a[i]==0) mpx[a[j]]=1;     // a[i] divides a[j] then a[j] can be placed in a[i]'s group
                    }
               }
          }
          cout<<ans<<endl;
    }

This code should become an O(n^2) approach when all pairs of array elements are non-divisible. How is it then passing the constraints?

Please give your consent that something is wrong or clarify me, please.
Thanks in advance.

2

Yes, this solution should definitely give TLE. There are more than 5x10^6 primes in the range of [1,10^8].
Maybe the TCs are weak.