CodeForces 577C Vasya and Petya's Game 数学

题意就是给你一个1到n的范围你每次可以问这个数是否可以被某一个数整除问你要猜多少数才能确定这个数……

一开始一点思路也没有后来查了一下才知道每个数都可以分为几个质数的整数次幂相乘得到……

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<math.h>
 5 #include<string.h>
 6 #include<string>
 7 #include<map>
 8 #include<vector>
 9 #include<queue>
10 #define M(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 int n;
13 bool prime[1005];
14 void init(){
15     for(int i=2;i<=n;i++){
16         if(!prime[i]){
17             if(i>n/i) continue;
18             for(int j=i*i;j<=n;j+=i)
19                 prime[j]=true;
20         }
21     }
22 }
23 int main(){
24     scanf("%d",&n);
25     init();
26     int num[1005],ans=0;
27     for(int i=2;i<=n;i++){
28         if(!prime[i]){
29             num[ans++]=i;
30             for(int j=i*i;j<=n;j*=i)
31                num[ans++]=j;
32         }
33     }
34     printf("%d
",ans);
35     for(int i=0;i<ans;i++)
36         printf("%d%c",num[i],i==ans-1?'
':' ');
37     return 0;
38 }