EOJ 1030

題目：

思路： 用class建立類友善排序及交換，預先創立素數數組防止時間複雜度過高，最後根據題目要求進行排序

問題： 送出後說我逾時了，但是檢查一遍并未發現可能逾時的循環

代碼：

#include <iostream>
#include<stdio.h>

using namespace std;
class p{
public:
    int a,b,ans;
};

int main()
{
    p num[10001];
    int n,nu,i,j,k,s1[10001]={0,-1};
    cin>>n;
    for(i=2;i<=10000;i++){
        for(j=2;j<i;j++){//對一個數來說，除數應當從2到它本身-1
            if(i%j==0){
                s1[i]=-1;
                //有一個除盡了，-1代表不是素數
                break;
            }

        }
        //if(s[i]==0)cout<<i<<endl;
    }
    int sn[10001]={0};//sn存儲素數數量
    for(i=1;i<=10000;i++){
        sn[i]=sn[i-1];
        if(s1[i]!=-1){
            sn[i]++;
        }
    }

    for(i=1;i<=n;i++){
        cin>>nu;
        for(j=1;j<=nu;j++){
                num[j].ans=0;
            cin>>num[j].a>>num[j].b;
            num[j].ans=sn[num[j].b]-sn[num[j].a-1];
        }
        for(j=1;j<nu;j++){
            for(k=1;k<nu;k++){
                if(num[k].ans>num[k+1].ans){
                    swap(num[k],num[k+1]);
                }
                if(num[k].ans==num[k+1].ans){
                    if(num[k].a>num[k+1].a){
                        swap(num[k],num[k+1]);
                    }else if(num[k].a==num[k+1].a&&num[k].b>num[k+1].b){
                        swap(num[k],num[k+1]);
                    }
                }
            }
        }
        printf("case #%d:\n",i-1);
        for(j=1;j<=nu;j++){
            cout<<num[j].a<<" "<<num[j].b<<endl;
        }
    }
}


           

end