Header Ads Widget

the prime cells

Problem:-

You are given a grid of size n×n filled with numbers in each of its cells. Now you need to count total cells in the grid such that the sum of the numbers on its top , left , right and bottom cells is a prime number. In case there is no cell in a particular direction assume the number to be as 0.
Input
First line contains a number n as input denoting size of the grid. Next n lines contain n numbers each denoting value of the elements of the grid in each row.
Output
In the output you have to give the count of total cells as described above.
Constraints
2n100
1g[i][j]100 where g[i][j] is the value in the grid at ith row and jth column.
SAMPLE INPUT
 
2
1 2
3 4
SAMPLE OUTPUT
 
4
Explanation
In the given grid if we pick the first element that is 1 then to its right and bottom are 2 and 3 whose sum is 5 and so its prime. Note that to the left there is no element so we consider it as 0 and same goes for the up direction. Checking this for all yields that all the four cells contribute to the count of cells whose sum of the adjacent cell values is prime.
Time Limit:2.0 sec(s) for each input file.
Memory Limit:256 MB
Source Limit:

solution:-

#include<stdio.h>
int prime(int n)
{
int i;
       for( i=2;i<n;i++)
{
         if(n%i==0)
         break;
}
       if(i==n)
         return 1;
        else
         return 0;
}
void main()
{
     int n,a[100][100],sum=0,s=0,i;
     scanf("%d",&n);
     for(int i=0;i<n;i++)
     {
        for(int j=0;j<n;j++)
         scanf("%d",&a[i][j]);

     }
     for(i=0;i<n;i++)
     {
        for(int j=0;j<n;j++)
        {
            if(i-1>=0)
             sum=sum+a[i-1][j];
            if(j-1>=0)
             sum=sum+a[i][j-1];
            if(i+1<n)
             sum=sum+a[i+1][j];
            if(j+1<n)
             sum=sum+a[i][j+1];
            if(prime(sum)==1)
             s++;
            sum=0;
        }
     }
     printf("%d",s);
}