codeforces #319 C - Vasya and Petya's Game (数学)
因为每一个正整数可以唯一分解质因数...
要看能猜多少次，只要知道不大于n的质因子数有多少个即可（相同的算多
由于n才是１０００．所以素数表随便搞就好....不用筛也行...
/*************************************************************************
> File Name: code/cf/#319/C.cpp
> Author: 111qqz
> Email: rkz2013@126.com
> Created Time: 2015年09月18日 星期五 20时29分00秒
************************************************************************/
1#include<iostream>
2#include<iomanip>
3#include<cstdio>
4#include<algorithm>
5#include<cmath>
6#include<cstring>
7#include<string>
8#include<map>
9#include<set>
10#include<queue>
11#include<vector>
12#include<stack>
13#include<cctype>
14#define y1 hust111qqz
15#define yn hez111qqz
16#define j1 cute111qqz
17#define ms(a,x) memset(a,x,sizeof(a))
18#define lr dying111qqz
19using namespace std;
20#define For(i, n) for (int i=0;i<int(n);++i)
21typedef long long LL;
22typedef double DB;
23const int inf = 0x3f3f3f3f;
24const int N=1E3+5;
25int pri[N];
26int cnt;
27int n;
28int ans[N];
29bool prime( int x)
30{
31 if (x<=3) return true;
32 for ( int i = 2 ; i *i <= x ; i++)
33 {
34 if (x%i==0) return false;
35 }
36 return true;
37}
38int main()
39{
40 #ifndef ONLINE_JUDGE
41 // freopen("in.txt","r",stdin);
42 #endif
43 ms(pri,0);
44 cnt = 0 ;
1 for ( int i = 2 ; i <= 1005 ; i++)
2 {
3 if (prime(i))
4 {
5 cnt++;
6 pri[cnt] = i ;
7 }
8 }
9 scanf("%d",&n);
10 ms(ans,0);
11 int num = 0 ;
12 for ( int i = 1 ; pri[i] <= n&&i<=cnt ; i++)
13 {
14 int tmp = pri[i];
15 while (tmp<=n)
16 {
17 num++;
18 ans[num] = tmp;
19 tmp = tmp * pri[i];
1 }
2 }
3 cout<<num<<endl;
4 for ( int i = 1 ; i <= num ; i++)
5 {
6 cout<<ans[i]<<" ";
7 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}