CodeForces 577C Vasya and Petya's Game 数学

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

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

 #include<stdio.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<map>
#include<vector>
#include<queue>
#define M(a,b) memset(a,b,sizeof(a))
using namespace std;
int n;
bool prime[];
void init(){
for(int i=;i<=n;i++){
if(!prime[i]){
if(i>n/i) continue;
for(int j=i*i;j<=n;j+=i)
prime[j]=true;
}
}
}
int main(){
scanf("%d",&n);
init();
int num[],ans=;
for(int i=;i<=n;i++){
if(!prime[i]){
num[ans++]=i;
for(int j=i*i;j<=n;j*=i)
num[ans++]=j;
}
}
printf("%d\n",ans);
for(int i=;i<ans;i++)
printf("%d%c",num[i],i==ans-?'\n':' ');
return ;
}
上一篇:iOS强制横屏或强制竖屏


下一篇:Click Models for Web Search(2) - Parameter Estimation