当前位置: 代码迷 >> 综合 >> CF679A Bear and Prime 100
  详细解决方案

CF679A Bear and Prime 100

热度:96   发布时间:2023-12-06 07:38:27.0

题目:Bear and Prime 100

思路:
一道交互题。
具体的,就是把1~50的质数都询问一遍。
如果被回答了两个及以上的"yes",那么显然这是一个合数。
如果没有"yes",那么是一个质数。
如果仅仅回答了一次"yes",则需要再次询问这个质数的平方能否整除这个数。

代码:

//test linux & test Interactive questions#include<bits/stdc++.h>
using namespace std;#define read(x) scanf("%d",&x)
#define maxn 100bool isprime[maxn+5]={
    0};int main(){
    int flg=0;for(int i=2;i<=maxn;i++) isprime[i]=true;for(int i=2;i<=maxn;i++) {
    if(isprime[i]){
    for(int j=2;j*i<=maxn;j++) {
    isprime[i*j]=false;}}}int whatnum=0;for(int i=2;i<=maxn/2;i++) {
    if(!isprime[i]) continue;printf("%d\n",i);char x[10];fflush(stdout);scanf("%s",x);if(x[0]=='y') flg++,whatnum=i;}if(flg==0) printf("prime");else if(flg==1) {
    if(whatnum*whatnum>maxn) printf("prime");else {
    printf("%d\n",whatnum*whatnum);char x[10];fflush(stdout);scanf("%s",x);if(x[0]=='y') printf("composite");else printf("prime");}} else printf("composite");return 0;
}