문제 설명
소타는 최근 재미있게 본 영화 포스터의 퍼즐을 구매하여 퍼즐을 맞추고 있었다. 문득 퍼즐 조각의 총 개수에 따라 만들 수 있는 퍼즐의 종류는 어떻게 달라질지 궁금해지게 되었다. 소타가 맞추던 퍼즐은 900피스인데, 가로는 25개, 세로는 36개로 구성되어있었는데, 가로 18, 세로 50개로 900피스 퍼즐을 만들 수도 있는 것이다. 퍼즐 조각의 개수가 입력되었을 때, 규격에 맞는 퍼즐이 몇 종류가 나올지 출력하는 프로그램을 만들어보자.
<퍼즐 규격>
-
퍼즐은 한 면에 최소 2개 이상의 조각이 있어야 한다.
-
따라서 퍼즐조각의 개수가 소수(약수가 1과 자기 자신뿐인 자연수)인 경우 가로x세로 형태로 만들 수 없기 때문에 퍼즐 규격에 맞지 않다.
-
퍼즐은 적당한 비율이 있어야 하는데 가로와 세로 길이가 서로 3배를 초과하지 않아야 한다.(예를 들어 가로가 3개, 세로가 11개로 구성된 퍼즐이라면 세로의 길이가 가로의 길이의 3배를 초과하기 때문에 규격에 맞지 않다.)
-
가로, 세로의 개수가 다르면 다른 퍼즐로 본다. 즉, 2x3과 3x2는 다른 퍼즐이다.
퍼즐 조각이 25개라면, 5x5 사이즈로 1개의 퍼즐밖에 만들 수 없다.
퍼즐 조각이 36개라면, 4x9, 6x6, 9x4 로 3개의 퍼즐을 만들 수 있다.
입력 설명
퍼즐 조각 개수(N)를 입력받는다. (0≤N≤2,147,483,647)
출력 설명
생성할 수 있는 퍼즐의 개수를 출력한다.(규격에 맞지 않을 경우 –1을 출력한다.)