열린 문의 갯수

N개의 방이 있고,  N명의 사람이 있다.

1 2 3 ... N-1 N

사람들은 순서대로 방 앞을 지나가면서 자기 번호의 배수에 해당하는 방문의 상태를 바꾼다.

(열려있으면-닫고, 닫혀있으면-열고)

ex) 2번째 사람 - 2,4,6,...번 방문의 상태를 바꾼다.

ex) 3번째 사람 - 3,6,9,...번 방문의 상태를 바꾼다.

처음엔 모든 방문이 닫혀있다.

모든 사람이 순서대로 열고 닫고 지나가면 마지막에는 몇개의 문이 열려있는지 답하라.

cin 전체 사람들의 수

cout 열려 있는 방문의 수

 

Hint : 방의 숫자 N의 약수의 개수가 짝수이면 마지막엔 닫혀있고,

홀수이면 마지막엔 열려있다.

         1~N사이의 수에서 약수의 개수가 홀수인 것의 개수를 찾으면 된다.

#include <iostream>

using namespace std;

int numofdivisors(int n) {

    int i, x=1;

    for(i=1;i<n;++i) if((n%i)==0) ++x;

    return x;

} 

int main() {

    int x=0, n;

    cout<<"N입력: ";

    cin>>n;

    for(int i=1;i<n+1;++i) 

        if((numofdivisors(i)%2)>0) x=x+1;

    cout<<"열린문의 갯수: "<< x << endl;

    return 0;

}