//第三部分
//将分母为n的最简分数，添加到数组pFareyArray中去
BOOL AddToFractionArray(int n,FareyArray *pFareyArray,
    PrimeTab *pPrimeTab,
    DivArea *pDivAreaTab,
    int nDiv,
    int maxIdx)
{
    BOOL bIsPrime;
    int j,j1,j2,k;
    Fraction  frac;
    DWORD t;
    bIsPrime=Farey_isPrime(n,pFareyArray,pPrimeTab);
    if ( bIsPrime)
    {
        for (j=1;j<n;j++)
        {
            frac.numerator=j;
            frac.denominator=n;
            k=j*nDiv/n;
            g_fareyArray.array.Data[pDivAreaTab[k].pt]=frac;
            pDivAreaTab[k].pt++;
        }
    }
    else
    {
        memset( g_fareyArray.pByteArray,0,g_fareyArray.byteArrayLen);
        //筛去和分母不互质的所有分子
        for (j1=0;j1<g_fareyArray.fac_count;j1++)
        {
            t=g_fareyArray.fac[j1];
            for (j2=t;j2<n;j2+=t)
                g_fareyArray.pByteArray[j2]=1;
        }
        
        for (j1=1;j1<n;j1++)
        {
            //仅仅将和n（分母）互质的数组成的分数添加到分数数组
            if (g_fareyArray.pByteArray[j1]==0)
            {
                frac.numerator=j1;
                frac.denominator=n;
                k=j1* nDiv /n;
                g_fareyArray.array.Data[pDivAreaTab[k].pt]=frac;
                pDivAreaTab[k].pt++;

            }
        }

    }
    return TRUE;
}

int SataticDistributeFarey(int n,
    FareyArray *pFarey,
    PrimeTab *pTab,
    DivArea *pDivTab,
    int nDiv)
{
    int i,j1,j2,s,k,count;
    BOOL bIsPrime;
    double t;
    //-------------------------    
    memset(pDivTab,0,sizeof(DivArea)*nDiv);

    count=0;
    //t=currTime();
    for (i=2;i<=n;i++)
    {
        bIsPrime=Farey_isPrime(i,pFarey,pTab);
        if ( bIsPrime)
        {
            count+=(i-1);
            for (j1=1;j1<i;j1++)
            {
                k=(j1 * nDiv/ i);
                pDivTab[k].count++;
            }
        }
        else
        {
            memset( g_fareyArray.pByteArray,0,g_fareyArray.byteArrayLen);
            for (j1=0;j1<g_fareyArray.fac_count;j1++)
            {
                s=g_fareyArray.fac[j1];
                for (j2=s;j2<i;j2+=s)
                    g_fareyArray.pByteArray[j2]=1;
            }
        
            for (j1=1;j1<i;j1++)
            {
                if (g_fareyArray.pByteArray[j1]==0)
                {
                        k=(j1 * nDiv/ i);
                        pDivTab[k].count++;
                    count++;
                }
            }
    
        }
    }
    
    for (i=1;i<nDiv;i++)
    {
        pDivTab[i].base=pDivTab[i-1].base+ pDivTab[i-1].count;
        pDivTab[i].pt=pDivTab[i].base;
    
    }
    
    //t=currTime()-t;
    #ifdef OUT_TIME
    printf("stat time=%.12f s\n",t);
    printf("count=%d scale=%.8f\n",count,(double)count/(double)n/(double)n);
    
    #endif
    return count;
}

//第四部分
void FareySequence(int n,char farey[])
{
    int i,nDiv,total;
    double t1,t2,t3;
    BOOL bRet;
    DivArea *pDivAreaTab=NULL;
    //----------------------------------
    
    farey[0]=0;
    
    total= n * n * 3/10;
    if (total<=1024)
        nDiv=1;
    else
    {
        double e =(int)( log((double)total)/log(2.00));
        nDiv= (1 << (int)(e/2));
    }

    bRet=PrimeTab_ReSift(&g_primeTab,n);
    if (!bRet)
        return;
    
    if (!Farey_Init(&g_fareyArray,n))
        return ;

    pDivAreaTab=new DivArea[nDiv];
    if (pDivAreaTab==NULL)
        return;
    
    total=SataticDistributeFarey(n,&g_fareyArray,&g_primeTab,pDivAreaTab,nDiv);
    FractionArray_setSize(&(g_fareyArray.array),total);

    #ifdef OUT_TIME
    t1=currTime();
    #endif
    for (i=2;i<=n;i++)
    {
        //printf("i=%d\n",i);
        bRet=AddToFractionArray(i,&g_fareyArray,&g_primeTab,pDivAreaTab,nDiv,total);
        if (!bRet)
            return;
    }
    g_fareyArray.array.count=g_fareyArray.array.size;
    #ifdef OUT_TIME
    t1=currTime()-t1;
    #endif
    

    #ifdef OUT_TIME
    t2=currTime();
    #endif
    FractionArray_Sort(&(g_fareyArray.array),pDivAreaTab,nDiv);
    
    #ifdef OUT_TIME
    t2=currTime()-t2;
    t3=currTime();
    #endif

    FractionArray_output(&(g_fareyArray),farey);
    #ifdef OUT_TIME
    t3=currTime()-t3;
    #endif

    FractionArray_Free(&(g_fareyArray.array));
    
    #ifdef OUT_TIME
    printf("calc time=%.12f s\nSort time=%.12f s\noutput time=%.12f s\n",t1,t2,t3);
    #endif
}



int main(int argc, char* argv[])
{
    
    int n;
    char *pBuff=NULL;
    char name[32]; 
    FILE *fp=NULL;

    InitData();

    while (1)
    {
        printf("n=?");
        scanf("%d",&n);
        if (n==0)
            break;
        pBuff=new char[n*n*4+4096];
        if (pBuff==NULL)
            return 0;
        FareySequence(n,pBuff);
        sprintf(name,"%d.txt",n);
        
        fp=fopen(name,"wt");
        fwrite(pBuff,1,strlen(pBuff),fp);
        fclose(fp);    
        delete[] pBuff;
    }

    FreeData();
    return 0;
}