b763

輸入說明 ：

輸入只有一行，一個數字N，代表學姊心裡想的數字介於 1~N 之間

輸出說明 ：

輸出有兩行，第一行M代表在最優秀的策略下你只要詢問M個問題就能猜中

第二行有由小到大排序好的M個數字X1 ~ XM ，代表阿倫會詢問學姊「你猜的數字是否會被Xi 整除呢?」

這題問的其實是,某個數以下,可以分解成哪些質數,和質數次方倍相乘

像45 ： 就有 2 3 4 5 7 8 9 11 13 16 17 19 23 25 27 29 31 32 36 37

也就是說45以下的質全部可以用上面的數字乘積表示出來

所以我先把1000以內的質數找出來,再把這些質數的次方倍不超過1000的找出來

之後查表即可

#include<stdio.h>
#include<math.h>
int main()
{
    int N;
    scanf("%d",&N);

    //建質數表 
    int p[1001];
    int i,j,k;

    for(i=0;i<1001;i++)
    {
        p[i]=1;
    }

    p[0]=0;
    p[1]=0;

    int temp =sqrt(1000);

    for(i=2;i<1001;i++)
        if(p[i])
        {
            for(j=i*i;j<1001;j+=i)
            p[j]=0;
        }

    //建質數次方表
    for(i=2;i<=temp;i++)
        if(p[i])
        {    j=i*i;
            while(j<=1000)
            {
                p[j]=1;
                j*=i;
            }
        }

    int count=0;

    for(i=2;i<=N;i++)
    {
        if(p[i])
        {
            count++;
        }
    }

    printf("%d\n",count);

    for(i=2;i<=N;i++)
    {
        if(p[i])
        {
            printf("%d ",i);
        }
    }
}