(13909) 창문 닫기

https://www.acmicpc.net/problem/13909

단계별로 풀어보기

15단계(약수, 배수와 소수 2) 9번째

 

 

 

수학 퀴즈 등에서도 자주 보이는 굉장히 유명한 문제

어떤 수 x번 창문을 여닫는 횟수는 x의 약수의 개수와 같다.

이때 p가 x의 약수라면 x/p도 x의 약수이므로 두번씩 여닫아 결과적으로 닫혀 있으며, 예외적으로 p=x/p일 때 한번만 여닫는다.

한마디로 x가 제곱수일 때 약수의 개수가 홀수이다(창문이 열려 있다).

 

 

 

#include <iostream>
using namespace std;

int main() 
{
  long n, res= 1;
  
  cin >> n;
  
  while(res*res<=n)  res++;
  
  cout << res-1;
  
  return 0;
}