#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:求教，那里错了 (3089) SHP00001 2007-08-25 14:12:51
  • Re:求教，那里错了 (19) SHP00001 2007-08-25 14:14:28