/*

     二分查找/暴力：先埃氏筛选预处理，然后暴力对于每一行每一列的不是素数的二分查找最近的素数，更新最小值

 */

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int MAXN = 5e2 + ;

 const int MAXM = 1e6 + ;

 const int INF = 0x3f3f3f3f;

 int a[MAXN][MAXN];

 int mn_r[MAXN];

 int mn_c[MAXN];

 bool is_prime[MAXM];

 int prime[MAXM];

 int n, m, x, y;

 int tot;

 void solve(void)

 {

     for (int i=; i<=1e6; ++i)    is_prime[i] = true;

     is_prime[] = false;

     for (int i=; i<=1e6; ++i)

     {

         if (is_prime[i])

         {

             prime[++tot] = i;

             for (int j=i*; j<=1e6; j+=i)    is_prime[j] = false;

         }

     }

 }

 bool check_r(void)

 {

     memset (mn_r, , sizeof (mn_r));

     bool ok = true;

     for (int i=; i<=n; ++i)

     {

         for (int j=; j<=m; ++j)

         {

             if (!is_prime[a[i][j]])

             {

                 ok = false;    mn_r[j]++;

             }

         }

     }

     return ok;

 }

 bool check_c(void)

 {

     memset (mn_c, , sizeof (mn_c));

     bool ok = true;

     for (int j=; j<=m; ++j)

     {

         for (int i=; i<=n; ++i)

         {

             if (!is_prime[a[i][j]])

             {

                 ok = false;    mn_c[j]++;

             }

         }

     }

     return ok;

 }

 int sum_r(void)

 {

     int ans = INF;    int tmp = ;

     for (int i=; i<=n; ++i)

     {

         tmp = ;    bool ok = true;

         for (int j=; j<=m; ++j)

         {

             if (!is_prime[a[i][j]])

             {

                 int p = lower_bound (prime+, prime++tot, a[i][j]) - prime;

                 if (p <= tot)    tmp += prime[p] - a[i][j];

                 else    {ok = false;    break;}

             }

         }

         if (ok) ans = min (ans, tmp);

     }

     return ans;

 }

 int sum_c(void)

 {

     int ans = INF;    int tmp = ;

     for (int j=; j<=m; ++j)

     {

         tmp = ;    bool ok = true;

         for (int i=; i<=n; ++i)

         {

             if (!is_prime[a[i][j]])

             {

                 int p = lower_bound (prime+, prime++tot, a[i][j]) - prime;

                 if (p <= tot)    tmp += prime[p] - a[i][j];

                 else    {ok = false;    break;}

             }

         }

         if (ok) ans = min (ans, tmp);

     }

     return ans;

 }

 int main(void)        //Codeforces Round #166 (Div. 2) B. Prime Matrix

 {

 //    freopen ("B.in", "r", stdin);

     solve ();

     while (scanf ("%d%d", &n, &m) == )

     {

         for (int i=; i<=n; ++i)

         {

             for (int j=; j<=m; ++j)

                 scanf ("%d", &a[i][j]);

         }

         if (check_r () || check_c ())    {puts ("");    continue;}

         else    printf ("%d\n", min (sum_r (), sum_c ()));

     }

     return ;

 }