PrimeFrequency.cpp

#include<bits/stdc++.h>
#define maxi 10000007

using namespace std;

int isprime[maxi],a[maxi],prmcnt[maxi];

void sieve(){
    fill_n(isprime,maxi,1);
    int i,j;
    isprime[0]=isprime[1]=0;
    a[0]=a[1]=0;
    for(i=2;i*i<=maxi;i++){
            if(isprime[i]==1){
              for(j=i*i;j<=maxi;j+=i){
                  isprime[j]=0;
                  a[j]=i;
         }
       }
    }
    prmcnt[0]=prmcnt[1]=0;
    for(i=2;i<=maxi;i++){
            if(isprime[i]==1){
                prmcnt[i]=1;
            }
            else{
                prmcnt[i]=1+prmcnt[i/a[i]];
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    sieve();
    cin>>t;
    while(t--){
            long long int n,t,ans=0;
    cin>>n;
    while(n--){
        cin>>t;
        ans+=prmcnt[t];
    }
    cout<<ans<<endl;
    }
    return 0;
}