hey, C++ (gcc) - rextester

Language: Layout:

//g++  7.4.0

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define boost ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int MAX = 1000001;

ll factor[MAX] = { 0 }; 
void generate() 
{ 
    factor[1] = 1;
    for (ll i = 2; i < MAX; i++) 
        factor[i] = i;

for (ll i = 4; i < MAX; i += 2) 
        factor[i] = 2;

// A modified version of Sieve of Eratosthenes to

// store the smallest prime factor that divides

// every number.

for (ll i = 3; i * i < MAX; i++) {
        if (factor[i] == i) { 
            for (ll j = i * i; j < MAX; j += i) { 
                if (factor[j] == j) 
                    factor[j] = i; 
            } 
        } 
    } 
} 
ll caf(ll n) 
{ 
    if (n == 1) 
        return 1;

int ans = 1;
    int dup = factor[n]; 
    int c = 1;

int j = n / factor[n];

while (j != 1) { 
        if (factor[j] == dup) 
            c += 1; 
        else { 
            dup = factor[j]; 
            ans = ans * (c + 1); 
            c = 1; 
          }
        j = j / factor[j]; 
    } 
    ans = ans * (c + 1); 
    return ans; 
} 
int main()
{boost;
/*int t;cin>>t;
while(t--)*/
ll n;
cin>>n;
ll a[n];
generate() ;
for(ll i=0;i<n;i++) cin>>a[i];

map<ll,ll>m,M;

for(ll i=0;i<n;i++) {
int c=caf(a[i]);
++m[c];
}
  //for(auto i:m) cout<<i.first<<" "<<i.second<<" ";

//for(int i=1;i<100;i++) cout<<caf(i) <<" ";

//for(auto i:M) cout<<i.first<<" "<<i.second<<" ";

int x=m[2],y=m[3],z=m[1],u=m[4];
cout<<(x+y-z-u)<<endl;
}

Show compiler warnings [ + ] Compiler args [ - ] Show input
Compilation time: 1.85 sec, absolute running time: 0.18 sec, cpu time: 0.03 sec, memory peak: 9 Mb, absolute service time: 2,2 sec