學會利用現成的資源很重要,在接到壹個以前沒做過的項目時,首先要做的就是在網上找找別人有沒遇到過類似的項目。找到就拿來,修改供己所用。呵呵,在樓上的基礎上進壹步修改。0?error(s),?0?warning(s)
#include<stdio.h>
#include<math.h>
int?number[210][5];?/*存放可逆素數及素數分解後的各位數字*/
int?select[110];?/*可以放在矩陣第壹行和最後壹行的素數的下標*/
int?array[4][5];?/*4X4的矩陣,每行0號元素存可逆素數對應的數組下標*/
int?count;?/*可逆素數的數目*/
int?selecount;?/*可以放在矩陣第壹行和最後壹行的可逆素數的數目*/
int?larray[2][200];?/*存放素數前二、三位數的臨時數組所對應的數量計數器*/
int?lcount[2];
int?num(int?number);
int?ok(int?number);
void?process(int?i);
void?copy_num(int?i);
int?comp_num(int?n);
int?find1(int?i);
int?find2(void);
int?find0(int?num);
void?p_array(void);
void?main()
{
int?i,k,flag,cc=0,i1,i4;
printf("there?are?magic?squares?with?invertable?primes?as?follw:\n");
for(i=1001;i<9999;i+=2)?/*求滿足條件的可逆素數*/
{
k=i/1000;
if(k%2!=0&&k!=5&&num(i))?/*若可逆素數的第壹位不是偶數或5*/
{
number[count][0]=i;?/*存入數組*/
process(count++);?/*分解素數的各位數字*/
if(number[count-1][2]%2!=0&&?/*若可逆素數滿足放在矩陣第壹行*/
number[count-1][3]%2!=0&&?/*和最後壹行的條件,記錄可逆素數的*/
number[count-1][2]!=5&&?/*下標,計數器加1*/
number[count-1][3]!=5)
select[selecount++]=count-1;
}
}
larray[0][lcount[0]++]=number[0][0]/100;?/*臨時數組的第壹行存前二位*/
larray[1][lcount[1]++]=number[0][0]/10;?/*臨時數組的第二行存前三位*/
for(i=1;i<count;i++)?/*將素數不重復的前二、三位存入臨時數組中*/
{
if(larray[0][lcount[0]-1]!=number[i][0]/100)
larray[0][lcount[0]++]=number[i][0]/100;
if(larray[1][lcount[1]-1]!=number[i][0]/10)
larray[1][lcount[1]++]=number[i][0]/10;
}
for(i1=0;i1<selecount;i1++)?/*在第壹行允許的匯聚圍內窮舉*/
{
array[0][0]=select[i1];?/*取對應的素數下標*/
copy_num(0);?/*復制分解的素數*/
for(array[1][0]=0;array[1][0]<count;array[1][0]++)?/*窮舉第二行*/
{
copy_num(1);?/*復制分解的數字*/
if(!comp_num(2))
continue;?/*若每列的前兩位的組成與素數相矛盾,則試探下壹個數*/
for(array[2][0]=0;array[2][0]<count;array[2][0]++)?/*窮舉第三行*/
{
copy_num(2);?/*復制分解的數字*/
if(!comp_num(3))
continue;?/*若每列的前三位的組成與素數相矛盾,則試探下壹個數*/
for(i4=0;i4<selecount;i4++)?/*在最後壹行允許的範圍內窮舉*/
{
array[3][0]=select[i4];
copy_num(3);?/*復制分解的數字*/
for(flag=1,i=1;flag&&i<=4;i++)?/*判斷每列是否可逆素數*/
if(!find1(i))flag=0;
if(flag&&find2())?/*判斷對角線是否為可逆素數*/
{?printf("No.%d\n",++cc);?p_array();?}?/*輸出幻方矩陣*/
}
}
}
}
}
int?num(int?number)?/*判斷是否可逆素數*/
{
int?j;
if(!ok(number))?return?0;
for(j=0;number>0;number/=10)?/*將素數變為反序數*/
j=j*10+number%10;
if(!ok(j))?return?0;?/*判斷反序數是否為素數*/
return?1;
}
int?ok(int?number)?/*判斷是否為素數*/
{
int?i;
double?j;
if(number%2==0)?return?0;
j=sqrt((double)number)+1;
for(i=3;i<=j;i+=2)
if(number%i==0)?return?0;
return?1;
}
void?process(int?i)?/*將第i個整數分解為數字並存入數組*/
{
int?j,num;
num=number[i][0];
for(j=4;j>=1;j--,num/=10)
number[i][j]=num%10;
}
void?copy_num(int?i)?/*將array[i][0]指向的素數的各位數字復制到array[i]中*/
{
int?j;
for(j=1;j<=4;j++)
array[i][j]=number[array[i][0]][j];
}
int?comp_num(int?n)?/*判斷array中每列的前n位是否與可逆素數允許的前n位矛盾*/
{
static?int?ii;?/*用內部靜態變量保存前壹次查找到的元素下標*/
static?int?jj;?/*ii:前壹次查找前二位的下標,jj:前壹次查找前三位的下標*/
int?i,num,k,*p;?/*p:指向對應的要使用的前壹次下標ii或jj*/
int?*pcount;?/*pcount:指向要使用的臨時數組數量的計數器*/
switch(n){?/*根據n的值選擇對應的壹組控制變量*/
case?2:pcount=&lcount[0];p=ⅈbreak;
case?3:pcount=&lcount[1];p=&jj;break;
default:return?0;
}
for(i=1;i<=4;i++)?/*對四列分別進行處理*/
{
for(num=0,k=0;k<n;k++)?/*計算前n位數字代表的數值*/
num=num*10+array[k][i];
if(num<=larray[n-2][*p])?/*與前壹次最後查找到的元素進行比較*/
for(;*p>=0&&num<larray[n-2][*p];(*p)--);/*若前次查找到的元素大,則向前找*/
else
for(;p<pcount&&num>larray[n-2][*p];(*p)++);?/*否則向後找*/
if(*p<0||*p>=*pcount)
{
*p=0;?return?0;
}
if(num!=larray[n-2][*p])
return?0;?/*前n位不是可逆素數允許的值則返回0*/
}
return?1;
}
int?find1(int?i)?/*判斷列方向是否是可逆素數*/
{
int?num,j;
for(num=0,j=0;j<4;j++)
num=num*10+array[j][i];
return?find0(num);
}
int?find2(void)?/*判斷對角線方向是否是可逆素數*/
{
int?num1,num2,i,j;
for(num1=0,j=0;j<4;j++)
num1=num1*10+array[j][j+1];
for(num2=0,j=0,i=4;j<4;j++,i--)
num2=num2*10+array[j][i];
if(find0(num1))?return(find0(num2));
else?return?0;
}
int?find0(int?num)?/*查找是否為滿足要求的可逆素數*/
{
static?int?j;
if(num<=number[j][0])for(;j>=0&&num<number[j][0];j--);
else?for(;j<count&&num>number[j][0];j++);
if(j<0||j>=count){?j=0;return?0;?}
if(num==number[j][0])?return?1;
else?return?0;
}
void?p_array(void)?/*輸出矩陣*/
{
int?i,j;
for(i=0;i<4;i++)
{
for(j=1;j<=4;j++)?printf("%d?",array[i][j]);
printf("\n");
}
}