http://codeforces.com/problemset/problem/577/C
问序列中最少含几个数 使得1-n的每一个数都能用序列中的几个数相乘得到
把每个数都素因子分解为(2^p1)*(3^p2)*(5^p3)...这种形式 把2^1...2^p1等都扔数组里去个重就好
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e3+10;
const int maxm=1e5+10;
int ans[maxm];
int n,tot;
int main()
{
int i,j,t,cur;
scanf("%d",&n);
for(i=2;i<=n;i++){
t=i;
for(j=2;j*j<=t;j++){
if(t%j==0){
cur=1;
while(t%j==0) t/=j,cur*=j;
ans[++tot]=cur;
}
}
if(t!=1) ans[++tot]=t;
}
sort(ans+1,ans+tot+1);
tot=unique(ans+1,ans+tot+1)-ans-1;
if(tot==0) printf("0\n");
else{
printf("%d\n",tot);
for(i=1;i<=tot;i++) printf("%d ",ans[i]);
printf("\n");
}
return 0;
}
