某个数x属于[1,n]，至少询问哪些数“x是否是它的倍数”才能判断x。
找出所有质因数和质因数的幂即可。
#include<cstdio>
#include<algorithm>
#define N 1005
using namespace std;
int n,pr[N],ans[N],cnt;
int main(){
scanf("%d",&n);
for(int i=2;i<=n;i++)
if(!pr[i])
for(int j=i*2;j<=n;j+=i)
pr[j]++;
for(int i=2;i<=n;i++)
if(pr[i]<2)
ans[cnt++]=i;
printf("%d\n",cnt);
for(int i=0;i<cnt;i++)
printf("%d ",ans[i]);
}
【CodeForces 577C】Vasya and Petya’s Game
原文：http://www.cnblogs.com/flipped/p/5701280.html