406 Prime Cuts

一次把範圍 1 ~ 1000 內的所有質數算出來，並用 array 紀錄，之後就不用再計算。

case 的計算時，找到的 prime number 在 lists 中從 index 1 開始，比較不會搞混。

印出的時候，把範圍算好，直接用一個 loop 全部印出。


#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int prime(int a){
    int i;

    for(i=2;i<=sqrt(a);i++){
        if(a%i==0)
            break;
    }

    return (i>sqrt(a)) ? 1 : 0;
}

int main(void){
    int num,c,i,amount;
    int lists[1000]={0},top;
    int ok[1001]={0};

    for(i=1;i<=1000;i++)
        if(prime(i)==1)
            ok[i]=1;
        else
            ok[i]=0;

    while(scanf("%d %d",&num,&c)!=EOF){
        top=0;
        for(i=1;i<=num;i++){
            if(ok[i]==1){
                lists[++top]=i;
            }
        }
        if(top%2==0)
            amount=c*2;
        else
            amount=c*2-1;

        printf("%d %d:",num,c);
        if(amount>top){
            for(i=1;i<=top;i++)
                printf(" %d",lists[i]);
        }else{
            if(top%2==0){
                for(i=top/2-(amount/2-1);i<=top/2+amount/2;i++)
                    printf(" %d",lists[i]);
            }else{
                for(i=top/2+1-(amount/2);i<=top/2+1+(amount/2);i++)
                    printf(" %d",lists[i]);
            }
        }

        printf("\n\n");
    }


    return 0;
}