埃式筛 自己在用点脑子就能写

说实话，ACGO的数据真的很水 我在ACGO里写的代码带到洛谷就错了…………
言归正传，这道题要先写一个埃式筛
代码：

   void ai(int maxn){ 
    memset(prime,true,sizeof(prime));
    prime[1]=0;
    for(int i=2;i<=maxn;++i){
        if(prime[i]){
            for(int j= i + i;j<=maxn;j += i){
            	prime[j]=0;
			} 
                
        }
    }
}
bool is_prime(long long x){
    return prime[x];
}

我喜欢再写一个is_prime
思路：
输入这个数 先判断这个数是否是质数 如果是的话输出1 再continue

int x;
		cin>>x;
        if(is_prime(x)){
            cout<<1<<endl;
            continue;
        }

作者写的时候把continue写成break 错了一直调不出来
继续我们写个while循环 由于没有出界条件就一直循环
一直减去2的i-1次幂 攻击次数加1
关键点来了
先判断下x是否比0小，如果比0小，说明它无法被打败 这就是-1的判断条件
后面有两个判断
1.正好减完了 也就是x为0 直接输出进攻次数，也就是我的ans
2.如果剩下是一个质数 魔法攻击一定是最优选择 因为他要最少攻击次数 砰一下就能给他干飞
想到上面↑这两种情况，做不出来…………回家种地吧……
最后再补一点细节

#include<bits/stdc++.h>
using namespace std;
bool prime[100005];
int t;
void ai(int maxn){ 
    memset(prime,true,sizeof(prime));
    prime[1]=0;
    for(int i=2;i<=maxn;++i){
        if(prime[i]){
            for(int j= i + i;j<=maxn;j += i){
            	prime[j]=0;
			} 
                
        }
    }
}
bool is_prime(long long x){
    return prime[x];
}
int main(){
    ai(100000);
	cin>>t;
	while(t--){
		int i=1,ans=0;
		int x;
		cin>>x;
        if(is_prime(x)){
            cout<<1<<endl;
            continue;
        }
		while(1){
			x-=(1<<i-1);
			ans++;
            
            if(x<0){
				cout<<-1<<endl;
				break;
			}
			if(x==0){
				cout<<ans<<endl;
				break;
			}
			else if(is_prime(x)){
				cout<<ans+1<<endl;
				break;
			}
            i++;
		}
	}
	return 0;
}

i和ans可以合起来写