> #include<stdio.h>
> #include<math.h>
> #include<string.h>
> #include<stdlib.h>
> #define MAX 150000
> int prime[MAX],gp[MAX][2],flag[MAX],d[MAX];
> void comput(int num)
> {
>     int big,little;
>     flag[num]=1;
>     big=sqrt(prime[num]);
>     little=sqrt(prime[num]-big*big);
>     gp[num][0]=little;
>     gp[num][1]=big;
> }
> void eld()
> {
>     int i,j,k,num;
>     prime[0]=2;
>     flag[0]=1;
>     prime[1]=3;
>     gp[1][0]=3;
>     gp[1][1]=0;
>     gp[0][0]=1;
>     gp[0][1]=1;
>     num=2;
>     for(i=4;i<1000000;i++)
>     {
>         k=0;
>         for(j=0;prime[j]<=sqrt(i);j++)
>         {
>             if(i%prime[j]==0)
>             {
>                 k=1;
>                 break;
>             }
>         }
>         if(k==0)
>         {
>             prime[num]=i;
>             if(i%4==1)
>             comput(num);
>             else
>             {
>                 gp[num][0]=prime[num];
>                 gp[num][1]=0;
>             }
>             num++;
>         }
>         if(num>=MAX)
>         break;
>     }
> }
>  int cmp(const void *a, const void *b)
>  {
>     int *p,*q,flag,i,j;
>     p=(int *)a;
>     q=(int *)b;
>     i=*p;
>     j=*q;
>     if(gp[i][0]==gp[j][0])
>     {
>         flag=gp[i][1]-gp[j][1];
>     }
>     else
>     {
>         flag=gp[i][0]-gp[j][0];
>     }
>     return flag;
>  }
> int main()
> {
>     int i,j,k,m,n,top;
>     memset(flag,0,sizeof(flag));
>     k=0;
>     eld();
>     while(scanf("%d",&n)!=EOF)
>     {
>         k++;
>         top=0;
>         if(n==1)//个人感觉不可能是1，我试了几次1的时候不输出，或输出1，或输出，j,-j都wa。。
>         printf("Case #%d: j, -j\n",k);
>         else{
>         printf("Case #%d:",k);
>         for(i=0;;i++)
>         {
>             if(n==1)
>             break;
>             else
>             {
>                 j=0;
>                 while(1)
>                 {
>                      if(n%prime[i]!=0)
>                      break;
>                      if(n%prime[i]==0)
>                      {
>                         j=1;
>                         n=n/prime[i];
>                      }
>                 }
>                 if(j==1)
>                 {
>                      d[top]=i;
>                      top++;
>                 }
>             }
>         }
>         qsort(d,top,sizeof(d[0]),cmp);
>         for(j=0;j<top;j++)
>         {
>             i=d[j];
>             if(j!=0)
>                 printf(",");
>             if(flag[i]==1)
>             {
>                 if(gp[i][1]==1)
>                 {
>                     printf(" %d+j, %d-j",gp[i][0],gp[i][0]);
>                 }
>                 else
>                 {
>                     printf(" %d+%dj, %d-%dj",gp[i][0],gp[i][1],gp[i][0],gp[i][1]);
>                 }
>             }
>             else
>             {
>                 printf(" %d",prime[i]);
>             }
>         }
>             printf("\n");
>         }
>     }
>     return 0;
> }

• Re:求教，那里错了 (19) SHP00001 2007-08-25 14:14:28