시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 83 30 25 53.191%

문제

상근이와 정인이는 숫자 맞추기 게임을 하고 있다.

먼저, 정인이는 1보다 크거나 같고, n보다 작거나 같은 자연수 하나를 생각한다.

상근이는 1보다 크거나 같고, n보다 작거나 같은 자연수 x를 정해 정인이에게 생각한 숫자가 x인지 물어볼 수 있다. 이때 정인이는 자신이 생각한 숫자와 x의 최대공약수가 몇 인지 말해준다.

다음은 n=6일 때 가능한 상근이와 정인이의 대화이다.

  • 상근: 3이야?
  • 정인: 3이랑 내가 생각한 숫자의 최대공약수는 1이야.
  • 상근: (음... 그럼 3이랑 6은 아니네? 근데 1,2,4,5는 될 수 있어!) 그럼 2야?
  • 정인: 2랑 내가 생각한 숫자의 최대공약수는 2야.
  • 상근: (오!? 그럼 1, 5는 아니겠네?) 너가 생각한 숫자는 4야 맞지?
  • 정인: 4랑 내가 생각한 숫자의 최대공약수는 2야.
  • 상근: 그럼 니가 생각한 숫자는 2네 ㅋㅋㅋ

위의 예에서 상근이는 정인이가 생각한 숫자를 맞추기 위해서 질문을 총 3번 했다. 하지만, n=6인 경우에 항상 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

제일 먼저 상근이는 6을 물어보면 된다. 만약 정인이가 1이라고 대답했다면, 정인이가 생각한 숫자는 1과 5중 하나이기 때문에, 2번 질문으로 맞출 수 있다. 정인이의 대답이 2라면, 정인이가 생각한 숫자는 2와 4중 하나이다. 만약, 정인이가 3이라고 대답했다면, 정답은 3이고, 6이라고 대답했다면 6이다.

따라서, 상근이는 최대 2번의 질문으로 정인이가 생각한 숫자를 맞출 수 있다.

n이 주어졌을 때, 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번 만에 정인이가 생각한 숫자를 맞출 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. 2 ≤ n ≤ 10,000

출력

첫째 줄에 상근이가 최적의 방법으로 질문했을 때, 최대 몇 번의 질문으로 정인이가 생각한 숫자를 맞출 수 있는지 출력한다.

예제 입력 1

6

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjM1MDEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNkNWNcdWIzMDBcdWFjZjVcdWM1N2RcdWMyMTggXHViOWRlXHVjZDk0XHVhZTMwIFx1YWM4Y1x1Yzc4NCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCBcdWMyMmJcdWM3OTAgXHViOWRlXHVjZDk0XHVhZTMwIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJhM2NcdWM4MDAsIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YjI5NCAxXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIG5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM3OTBcdWM1ZjBcdWMyMTggXHVkNTU4XHViMDk4XHViOTdjIFx1YzBkZFx1YWMwMVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgblx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOCB4XHViOTdjIFx1YzgxNVx1ZDU3NCBcdWM4MTVcdWM3NzhcdWM3NzRcdWM1ZDBcdWFjOGMgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YWMwMCB4XHVjNzc4XHVjOWMwIFx1YmIzY1x1YzViNFx1YmNmYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMgXHVjODE1XHVjNzc4XHVjNzc0XHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNjQwIHhcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHVhYzAwIFx1YmE4NyBcdWM3NzhcdWM5YzAgXHViOWQwXHVkNTc0XHVjOTAwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWM3NDAgbj02XHVjNzdjIFx1YjU0YyBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVjNjQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWIzMDBcdWQ2NTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+XHVjMGMxXHVhZGZjOiAzXHVjNzc0XHVjNTdjPzxcL2xpPlxyXG5cdDxsaT5cdWM4MTVcdWM3Nzg6IDNcdWM3NzRcdWI3OTEgXHViMGI0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWM3NTggXHVjZDVjXHViMzAwXHVhY2Y1XHVjNTdkXHVjMjE4XHViMjk0IDFcdWM3NzRcdWM1N2MuPFwvbGk+XHJcblx0PGxpPlx1YzBjMVx1YWRmYzogKFx1Yzc0Yy4uLiBcdWFkZjhcdWI3ZmMgM1x1Yzc3NFx1Yjc5MSA2XHVjNzQwIFx1YzU0NFx1YjJjOFx1YjEyND8gXHVhZGZjXHViMzcwIDEsMiw0LDVcdWIyOTQgXHViNDIwIFx1YzIxOCBcdWM3ODhcdWM1YjQhKSBcdWFkZjhcdWI3ZmMgMlx1YzU3Yz88XC9saT5cclxuXHQ8bGk+XHVjODE1XHVjNzc4OiAyXHViNzkxIFx1YjBiNFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCAyXHVjNTdjLjxcL2xpPlxyXG5cdDxsaT5cdWMwYzFcdWFkZmM6IChcdWM2MjQhPyBcdWFkZjhcdWI3ZmMgMSwgNVx1YjI5NCBcdWM1NDRcdWIyYzhcdWFjYTBcdWIxMjQ/KSBcdWIxMDhcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCA0XHVjNTdjIFx1YjlkZVx1YzljMD88XC9saT5cclxuXHQ8bGk+XHVjODE1XHVjNzc4OiA0XHViNzkxIFx1YjBiNFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHVjNzU4IFx1Y2Q1Y1x1YjMwMFx1YWNmNVx1YzU3ZFx1YzIxOFx1YjI5NCAyXHVjNTdjLjxcL2xpPlxyXG5cdDxsaT5cdWMwYzFcdWFkZmM6IFx1YWRmOFx1YjdmYyBcdWIyYzhcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCAyXHViMTI0IFx1MzE0Ylx1MzE0Ylx1MzE0YjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzcwNFx1Yzc1OCBcdWM2MDhcdWM1ZDBcdWMxMWMgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjlkZVx1Y2Q5NFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjOWM4XHViYjM4XHVjNzQ0IFx1Y2QxZCAzXHViYzg4IFx1ZDU4OFx1YjJlNC4gXHVkNTU4XHVjOWMwXHViOWNjLCBuPTZcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwIFx1ZDU2ZFx1YzBjMSAyXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODFjXHVjNzdjIFx1YmEzY1x1YzgwMCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgNlx1Yzc0NCBcdWJiM2NcdWM1YjRcdWJjZjRcdWJhNzQgXHViNDFjXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIDFcdWM3NzRcdWI3N2NcdWFjZTAgXHViMzAwXHViMmY1XHVkNTg4XHViMmU0XHViYTc0LCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1YjI5NCAxXHVhY2ZjIDVcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgMlx1YmM4OCBcdWM5YzhcdWJiMzhcdWM3M2NcdWI4NWMgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1Yzc1OCBcdWIzMDBcdWIyZjVcdWM3NzQgMlx1Yjc3Y1x1YmE3NCwgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWIyOTQgMlx1YzY0MCA0XHVjOTExIFx1ZDU1OFx1YjA5OFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgM1x1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWIzMDBcdWIyZjVcdWQ1ODhcdWIyZTRcdWJhNzQsIFx1YzgxNVx1YjJmNVx1Yzc0MCAzXHVjNzc0XHVhY2UwLCA2XHVjNzc0XHViNzdjXHVhY2UwIFx1YjMwMFx1YjJmNVx1ZDU4OFx1YjJlNFx1YmE3NCA2XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWNkNWNcdWIzMDAgMlx1YmM4OFx1Yzc1OCBcdWM5YzhcdWJiMzhcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzc4XHVjNzc0XHVhYzAwIFx1YzBkZFx1YWMwMVx1ZDU1YyBcdWMyMmJcdWM3OTBcdWI5N2MgXHViOWRlXHVjZDljIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YzgwMVx1Yzc1OCBcdWJjMjlcdWJjOTVcdWM3M2NcdWI4NWMgXHVjOWM4XHViYjM4XHVkNTg4XHVjNzQ0IFx1YjU0YywgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWJjODggXHViOWNjXHVjNWQwIFx1YzgxNVx1Yzc3OFx1Yzc3NFx1YWMwMCBcdWMwZGRcdWFjMDFcdWQ1NWMgXHVjMjJiXHVjNzkwXHViOTdjIFx1YjlkZVx1Y2Q5YyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMiAmbGU7IG4gJmxlOyAxMCwwMDA8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWNkNWNcdWM4MDFcdWM3NTggXHViYzI5XHViYzk1XHVjNzNjXHViODVjIFx1YzljOFx1YmIzOFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHViYzg4XHVjNzU4IFx1YzljOFx1YmIzOFx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NzhcdWM3NzRcdWFjMDAgXHVjMGRkXHVhYzAxXHVkNTVjIFx1YzIyYlx1Yzc5MFx1Yjk3YyBcdWI5ZGVcdWNkOWMgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzUwMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdDRCBHdWVzc2luZyBHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5QYXVsIGhhZCBhIGJpcnRoZGF5IHllc3RlcmRheSwgYW5kIHRoZXkgd2VyZSBwbGF5aW5nIGEgZ3Vlc3NpbmcgZ2FtZSB0aGVyZSB3aXRoIEFuZHJldzogQW5kcmV3IHdhcyB0cnlpbmcgdG8gZ3Vlc3MgUGF1bCZyc3F1bztzIGFnZS4gQW5kcmV3IGtuZXcgdGhhdCBQYXVsJnJzcXVvO3MgYWdlIGlzIGFuIGludGVnZXIgYmV0d2VlbiAxIGFuZCBuLCBpbmNsdXNpdmUuIEFuZHJldyBjYW4gZ3Vlc3MgYW55IG51bWJlciB4IGJldHdlZW4gMSBhbmQgbiwgYW5kIFBhdWwgd2lsbCB0ZWxsIGhpbSB3aGF0IGlzIHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiB4IGFuZCBoaXMgYWdlLjxcL3A+XHJcblxyXG48cD5IZXJlJnJzcXVvO3MgYSBwb3NzaWJsZSBjb3Vyc2Ugb2YgdGhlIGdhbWUgZm9yIG4gPSA2LiBBbmRyZXcgc3RhcnRzIHdpdGggZ3Vlc3NpbmcgMywgYW5kIFBhdWwgcmVwbGllcyB0aGF0IHRoZSBncmVhdGVzdCBjb21tb24gZGl2aXNvciBvZiAzIGFuZCBoaXMgYWdlIGlzIDEuIFRoYXQgbWVhbnMgdGhhdCBQYXVsJnJzcXVvO3MgYWdlIGNhbiZyc3F1bzt0IGJlIDMgb3IgNiwgYnV0IGNhbiBzdGlsbCBiZSAxLCAyLCA0IG9yIDUuIEFuZHJldyBjb250aW51ZXMgd2l0aCBndWVzc2luZyAyLCBhbmQgUGF1bCByZXBsaWVzIDIuIFRoYXQgbWVhbnMgdGhhdCBQYXVsJnJzcXVvO3MgYWdlIGNhbiZyc3F1bzt0IGJlIDEgb3IgNSwgYW5kIHRoZSBvbmx5IHR3byByZW1haW5pbmcgY2hvaWNlcyBhcmUgMiBhbmQgNC4gRmluYWxseSwgQW5kcmV3IGd1ZXNzZXMgNCwgYW5kIFBhdWwgcmVwbGllcyAyLiBUaGF0IG1lYW5zIHRoYXQgUGF1bCZyc3F1bztzIGFnZSBpcyAyLCBhbmQgdGhlIGdhbWUgaXMgb3Zlci48XC9wPlxyXG5cclxuPHA+QW5kcmV3IG5lZWRlZCB0aHJlZSBndWVzc2VzIGluIHRoZSBhYm92ZSBleGFtcGxlLCBidXQgaXQmcnNxdW87cyBwb3NzaWJsZSB0byBhbHdheXMgZGV0ZXJtaW5lIFBhdWwmcnNxdW87cyBhZ2UgaW4gYXQgbW9zdCB0d28gZ3Vlc3NlcyBmb3IgbiA9IDYuIFRoZSBvcHRpbWFsIHN0cmF0ZWd5IGZvciBBbmRyZXcgaXM6IGF0IHRoZSBcdWZiMDFyc3Qgc3RlcCwgZ3Vlc3MgNi4gSWYgUGF1bCBzYXlzIDEsIHRoZW4gaXRzIDEgb3IgNSBhbmQgaGUgY2FuIGNoZWNrIHdoaWNoIG9uZSBieSBndWVzc2luZyA1LiBJZiBQYXVsIHNheXMgMiwgdGhlbiBpdHMgMiBvciA0LCBhbmQgaGUgY2FuIGNoZWNrIGJ5IGd1ZXNpbmcgNCBhcyB3ZSZyc3F1bzt2ZSBzZWVuIGFib3ZlLiBJZiBQYXVsIHNheXMgMywgdGhlbiB3ZSBhbHJlYWR5IGtub3cgdGhlIGFuc3dlciBpcyAzLiBGaW5hbGx5LCBpZiBQYXVsIHNheXMgNiwgdGhlIGFuc3dlciBpcyA2LjxcL3A+XHJcblxyXG48cD5XaGF0IGlzIHRoZSBudW1iZXIgb2YgZ3Vlc3NlcyByZXF1aXJlZCBpbiB0aGUgd29yc3QgY2FzZSBpZiBBbmRyZXcgZ3Vlc3NlcyBvcHRpbWFsbHkgZm9yIHRoZSBnaXZlbiBuPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IFx1ZmIwMWxlIGNvbnRhaW5zIG9uZSBpbnRlZ2VyIG4sIDIgJmxlOyBuICZsZTsgMTAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCBvbmUgaW50ZWdlciAmbWRhc2g7IHRoZSBudW1iZXIgb2YgZ3Vlc3NlcyBBbmRyZXcgd2lsbCBuZWVkIHRvIG1ha2UgaW4gdGhlIHdvcnN0IGNhc2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ICPC > Regionals > Northern Eurasia > Northern Eurasia Finals > NEERC 2011 G번