Primprim - 91 p

#include <fstream>
using namespace std;

ifstream cin("primprim.in");
ofstream cout("primprim.out");

#define MAX_ELEM 1000000
int v[MAX_ELEM+1],dif[MAX_ELEM+1];
int vd[1000000];
int frv[100];

void calcul_dif(){
    int i,j;
    v[0]=v[1]=1;
    for(i=2;i*i<=MAX_ELEM;i++){
        if(v[i]==0){
            for(j=i*i;j<=MAX_ELEM;j+=i){
                v[j]=1;
            }
        }
    }
    dif[0]=2;
    dif[1]=1;
    j=2;
    for(i=2;i<=MAX_ELEM;i++){
        if(v[i]==0)
            j=i;
        dif[i]=i-j;
    }
    j=3*MAX_ELEM;
    for(i=MAX_ELEM;i>=0;i--){
        if(v[i]==0)
            j=i;
        dif[i]=min((int)dif[i],j-i);
    }
}

int main()
{
    int n,cer,s,a,i,poz,k,n1,m;
    cin>>cer>>n;
    calcul_dif();
    if(cer==1){
        s=0;
        for(i=0;i<n;i++){
            cin>>a;
            s+=dif[a];
        }
        cout<<s;
    }else{
        for(i=0;i<n;i++){
            cin>>vd[i];
            frv[dif[vd[i]]]++;
        }
        cin>>n1;
        for(m=0;m<n1;m++){
            cin>>poz>>a>>k;
            frv[dif[vd[poz-1]]]--;
            vd[poz-1]=a;
            frv[dif[vd[poz-1]]]++;
            s=i=0;
            while(k>0){
                if(frv[i]<k){
                    k-=frv[i];
                    s+=frv[i]*i;
                }else{
                    s+=k*i;
                    k=0;
                }
                i++;
            }
            cout<<s<<"\n";
        }
    }
    return 0;
}