양의 정수 X에 대해 길이가 m이고 X-인수 체인이라 함은 다음을 말한다.

1 = X_0, X_1, X_2, …, X_m = X(이를 설명하면, X_0 = 1, X_m = X 라는 뜻이며 X_1 , ... X_{m-1} : 임의의 양의 정수를 뜻한다.)

위의 X-인수 체인에 존재하는 숫자는 아래의 조건을 만족해야 한다. X_i < X_{i+1}, X_i | X_{i+1}(a|b라는 것은 a가 b를 완전히 나누어 떨어지게 한다는 것이다.)

정수 X를 입력받아 X-인수 체인의 최대 길이와, 최대 길이를 이루는 체인이 몇 가지 있는지 알아보는 프로그램을 작성하라.

X-인수 체인 timer 1s memory 128MB

X-인수 체인 1s 128MB