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