시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 21 10 9 69.231%

문제

메르센 수는 2P-1 (P는 소수) 인 수를 말한다.

메르센 수는 P가 작을 땐 모두 소수인 듯 보인다.

Prime Corresponding Mersenne Number
2 4-1 = 3 - prime
3 8-1 = 7 - prime
5 32-1 = 31 - prime
7 128-1 = 127 - prime

하지만 P가 충분히 큰 소수일 경우, 메르센 수는 소수가 아닐 수도 있다.

이렇게 메르센 수이면서 소수가 아닌 수를 '메르센 합성수' 라 하자.

이 때, K(< 63)가 주어지면, P가 K 이하인 모든 메르센 합성수를 찾아 소인수분해하는 프로그램을 작성하여라.

입력

입력에는 단 하나의 정수 K가 주어진다. (K < 63)

출력

P<=K 인 모든 메르센 합성수 2 P-1에 대해, 예제 출력과 같은 형식으로 소인수분해한 결과를 출력한다.

메르센 합성수 자체가 작은 수부터 출력해야 하며, 각 소인수들은 오름차순으로 출력되어야 한다.

예제 입력

31

예제 출력

23 * 89 = 2047 = ( 2 ^ 11 ) - 1
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1

힌트