You've got an nXm matrix. The matrix
consists of integers. In one move, you can apply a single transformation to the
matrix: choose an arbitrary element of the matrix and increase it by 1. Each
element can be increased an arbitrary number of times.
You are really curious about prime
numbers. Let us remind you that a prime number is a positive integer that has
exactly two distinct positive integer divisors: itself and number one. For
example, numbers 2, 3, 5 are prime and numbers 1, 4, 6 are not.
A matrix is prime if at least one of
the two following conditions fulfills:
- the matrix has a row with prime
numbers only;
- the matrix has a column with
prime numbers only;
Your task is to count the minimum
number of moves needed to get a prime matrix from the one you've got.
Input
The first line contains two integers
n, m(1<=n, m<=500),the number of rows and columns in the matrix,
correspondingly. Each of the following n lines contains m integers, the initial
matrix. All matrix elements are positive integers. All numbers in the initial
matrix do not exceed 105.
The numbers in the lines are
separated by single spaces.
Output
Output
Print a single integer, the minimum
number of moves needed to get a prime matrix from the one you've got. If you've
got a prime matrix, print 0.
Program
int isprime(int); /* function prototype */
int main()
{
int i, j, num, count, row_rount, column_count, n, m, p;
printf("input n and m"); /* n=no.of rows m=no.of columns */
scanf("%d%d",&n,&m);
int a[n][m];
printf("enter elements of matrix");
for(i=0;i<n;i++) /* reading matrix elements */
{
for(j=0;j<m;j++)
{
scanf("%d",&a[i][j]);
}
}
row_rount=10000;
column_count=10000;
for(i=0;i<n;i++)
{
count=0;
for(j=0;j<m;j++)
{
num=a[i][j];
p=isprime(num);
while(p==0) /* if not prime */
{
num++;
count++;
p=isprime(num);
}
}
if(count<row_rount)
{
row_rount=count;
}
}
{
count=0;
for(i=0;i<n;i++)
{
p=isprime(num);
while(p==0) /* if not prime */
{
num++;
count++;
p=isprime(num);
}
}
if(count<column_count)
{
column_count=count;
}
}
if(row_rount<column_count)
printf("%d",row_rount);
else printf("%d",column_count);
return 0;
}
int isprime(int num)
{
int prime[30]={0};
int i,x;
prime[0]=2;
prime[1]=3;
if(num==1)
return 0;
else if((num==2)||(num==3))
return 1;
else
{
while((prime[i])!=0)
{
if(num%prime[i]==0)
x=0;
i++;
}
if(x==1)
return 1;
else return 0;
}
}
Sample Input 1
3 3
1 2 3
5 6 1
4 4 1
Sample Output 1
1
