我用的米勒拉宾素性检测+快速傅里叶变换(FFT)，TLE了

#include<iostream>
#include<cmath>
#include<vector>
#include<complex>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
typedef complex<double> cd;
const double PI=acos(-1);
int s[1005][1005];
void fft(vector<cd>& a,bool invert) 
{
    int n=a.size();
    if(n==1)
		return;
    vector<cd> a0(n / 2),a1(n / 2);
    for(int i=0;i<n/2;i++)
        a0[i] = a[i*2],a1[i] = a[i*2 + 1];
    fft(a0,invert);
    fft(a1,invert);
    double angle=2*PI/n*(invert?-1:1);
    cd w(1),wn(cos(angle),sin(angle));
    for(int i=0;i<n/2;i++) 
	{
        a[i]=a0[i]+w*a1[i];
        a[i+n/2]=a0[i]-w*a1[i];
        if (invert)
            a[i]/=2,a[i+n/2]/=2;
        w *= wn;
    }
}
vector<ll> multiply(const vector<ll>& a, const vector<ll>& b) 
{
    vector<cd>fa(a.begin(),a.end()),fb(b.begin(),b.end());
    int n=1;
    while(n<a.size()+b.size()) 
		n<<=1;
    fa.resize(n);
    fb.resize(n);
    fft(fa, false);
    fft(fb, false);
    for(int i=0;i<n;i++)
        fa[i]*=fb[i];
    fft(fa,true);
    vector<ll>result(n);
    for (int i=0;i<n;i++)
        result[i]=llround(fa[i].real());
    ll carry=0;
    for (int i=0;i<n;i++) 
	{
        result[i]+=carry;
        carry=result[i]/10;
        result[i]%=10;
    }
    while (result.size()>1&&result.back()==0)
        result.pop_back();
    return result;
}
vector<ll> mod_pow_fft(const vector<ll>& base, ll exp, const vector<ll>& mod) 
{
    vector<ll> result = {1};
	vector<ll> b = base;
    while(exp>0) 
	{
        if(exp%2==1) 
		{
            result=multiply(result,b);
            result.resize(mod.size());
            for(size_t i=0;i<mod.size();i++)
                result[i] %= mod[i];
        }
        b=multiply(b,b);
        b.resize(mod.size());
        for (size_t i=0;i<mod.size();i++)
            b[i] %= mod[i];
        exp>>=1;
    }
    return result;
}
bool miller_rabin_test_fft(ll n,ll d) 
{
	vector<ll> base={2+rand()%(n-4)};
    vector<ll> mod={n};
    vector<ll> x=mod_pow_fft(base,d,mod);
    if(x==vector<ll>{1}||x==vector<ll>{n - 1})
        return true;
    while(d!=n-1) 
	{
        x=multiply(x, x);
        x.resize(mod.size());
        for (size_t i=0;i<mod.size();i++)
            x[i] %= mod[i];
        d*=2;
        if(x==vector<ll>{1}) 
			return false;
        if(x==vector<ll>{n-1}) 
			return true;
    }
    return false;
}
bool is_prime_fft(ll n,int k) 
{
    if (n<=1||n==4)
		return false;
    if (n<=3)
		return true;
    ll d=n-1;
    while(d%2==0)
		d/=2;
    for (int i=0;i<k;i++) 
        if (!miller_rabin_test_fft(n, d))
            return false;
    return true;
}
int mi(int num) 
{
    int operations=0;
    while (!is_prime_fft(num,5)) 
        num++,operations++;
    return operations;
}
int mi(vector<int>& line) 
{
    int ops=0;
    for(int num:line)
        ops+=mi(num);
    return ops;
}

int main() 
{
	freopen("matrices.in","r",stdin);
	freopen("matrices.out","w",stdout);
    srand(time(0));
    int n, m;
    scanf("%d%d",&n,&m);
    vector<vector<int>> ma(n, vector<int>(m));

    for (int i=0;i<n;i++) 
        for (int j=0;j<m;j++)
            scanf("%d",&ma[i][j]);
    int mi2=2e9;
    for (int i=0;i<n;i++) 
        mi2=min(mi2,mi(ma[i]));
    for (int j=0;j<m;j++) {
    	vector<int> c(n);
        for(int i=0;i<n;i++)
            c[i]=ma[i][j];
        mi2=min(mi2,mi(c));
    }
	printf("%d",mi2);
}