本部校赛蛇形填数（二）problen1338

Description

萌萌哒cy学姐参加去年的新生杯的时候，蛇形矩阵那题被她分分钟秒掉，于是她决定出一个更难的题目，她要求矩阵里的每个数都是质数，当然，蛇形的规则也略有变化

如2*3矩阵：

2 7 11

3 5 13

再如3*4的矩阵

2 13 17 37

3 11 19 31

5 7 23 29

Input

第一行为一个正整数T，表示数据的组数，接下来T行，每行两个正整数n,m，表示矩阵有n行m列

Output

对于每一个输入输出n行，每行m个数，表示这个矩阵，输出内容见题目描述,每个数输出宽度为6

Sample Input

2
2 3
3 4

Sample Output

     2     7    11
     3     5    13
     2    13    17    37
     3    11    19    31
     5     7    23    29

Hint

1<=n,m<=100

超时代码：哭晕

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4  int zhi(int num)
 5 {
 6     int i,j,p,h=0;
 7     static int k=3;
 8     for(i=k;;i++)
 9     {
10         int p=sqrt(i);
11         for(j=2;j<=p;j++)
12         {
13             if(i%j==0)
14             break;
15         }
16         if(j<=p)
17             continue;
18            k=i+1;
19         return i;
20     }
21 }
22 int main()
23 {
24         
25    int a[20][20];
26    int m,n,x,y;
27    int T;
28    scanf("%d",&T);
29    while(T--)
30    {
31         scanf("%d%d",&m,&n);
32         {
33             memset(a,0,sizeof(a));
34             int count=0;
35             a[x=0][y=0]=2;
36             while(1)
37             {
38                 while(!a[x+1][y]&&x+1<m)
39                     a[++x][y]=zhi(++count);
40                 while(!a[x][y+1]&&y+1<n)
41                     a[x][++y]=zhi(++count);
42                 while(!a[x-1][y]&&x-1>=0)
43                     a[--x][y]=zhi(++count);
44                 while(!a[x][y-1]&&y-1>=0)    
45                     a[x][--y]=zhi(++count);
46                 if(count==m*n-1)
47                     break;
48             }
49         for(x=0;x<m;x++)
50             {
51                 for(y=0;y<n;y++)
52                     printf("%6d",a[x][y]);
53                 printf("
");
54             }
55         }
56   }
57     
58 }

AC代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 int b[100000];
 5 int z()//求素数 
 6 {
 7     int i,j,count=0;
 8     for(i=2;;i++)
 9     {
10         int k=sqrt(i);
11         for(j=2;j<=k;j++)
12         {
13             if(i%j==0)
14                 break;
15         }
16         if(j<=k)
17             continue;
18             
19         b[count]=i;
20         count++;
21         if(count==10000)
22             break;
23     }
24 }
25 int main()
26 {
27         
28     int a[100][100];
29     int m,n,x,y;
30     int T;
31     scanf("%d",&T);
32     z();
33     while(T--)
34     {
35         scanf("%d%d",&m,&n);
36     
37         memset(a,0,sizeof(a));
38         int count=0;
39         a[x=0][y=0]=2;
40         while(count<m*n-1)
41         {
42             while(!a[x+1][y]&&x+1<m)
43                 a[++x][y]=b[++count];
44             while(!a[x][y+1]&&y+1<n)
45                 a[x][++y]=b[++count];
46             while(!a[x-1][y]&&x-1>=0)
47                 a[--x][y]=b[++count];
48             while(!a[x][y-1]&&y-1>=0)    
49                 a[x][--y]=b[++count];
50         }
51         for(x=0;x<m;x++)
52             {
53                 for(y=0;y<n;y++)
54                     printf("%6d",a[x][y]);
55                 printf("
");
56             }
57         
58     }
59     
60 }

本部校赛 蛇形填数（二）problen1338

本部校赛蛇形填数（二）problen1338