CF 576A 猜数

A给出一个数x，B每次猜一个y，A回答B，x是否可以被y整除，求出要猜的最小次数和需要猜的数。

枚举每个素数p，可以知道如果p^k<=n，则p^k一定需要选

Sample test(s)
input
4
output
3
2 4 3
input
6
output
4
2 4 3 5

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <string>
 6 # include <cmath>
 7 # include <queue>
 8 # include <list>
 9 # define LL long long
10 using namespace std ;
11 
12 int ans[1010] ;
13 
14 bool isp (int val )
15 {
16      int i ;
17      if (val == 1)
18        return 0 ;
19      for (i = 2 ; i*i <= val ; i++)
20      {
21          if (val % i == 0)
22              return 0 ;
23      }
24      return 1 ;
25 
26 }
27 
28 int main()
29 {
30     //freopen("in.txt","r",stdin) ;
31     int n ;
32     while(scanf("%d",&n ) != EOF)
33     {
34         int i ;
35         int l = 0 ;
36         if (n == 1)
37         {
38             printf("0
") ;
39             continue ;
40         }
41 
42         for (i = 2 ; i <= n ; i++)
43         {
44             if (isp(i) == 0)
45                 continue ;
46             int p = i ;
47             while(p <= n)
48             {
49                 ans[l] = p ;
50                 l++ ;
51                 p *= i ;
52             }
53         }
54         printf("%d
" , l) ;
55         for (i = 0 ; i < l-1 ; i++)
56             printf("%d " , ans[i]) ;
57         printf("%d
" , ans[i]) ;
58     }
59 
60 
61 
62     return 0;
63 }

View Code