메르센 합성수

시간 제한1초메모리 제한128 MB

요약

K 이하의 소수 P에 대해 합성수인 메르센 수 2^P - 1을 모두 소인수분해해서 작은 수부터 출력합니다.

문제

메르센 수는 소수 $P$ 에 대해 $2^P - 1$ 꼴로 쓰는 수다.

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

하지만 $P$ 가 충분히 큰 소수이면 메르센 수가 소수가 아닐 수도 있다. 이렇게 소수가 아닌 메르센 수를 메르센 합성수라 하자.

정수 $K$ 가 주어지면 $P \le K$ 인 메르센 합성수를 모두 찾아 소인수분해하는 프로그램을 작성하시오.

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

$P \le K$ 인 메르센 합성수 $2^P - 1$ 을 모두 소인수분해해서 한 줄에 하나씩 출력한다. 각 줄의 형식은 다음과 같다.

q1 * q2 * ... * qm = M = ( 2 ^ P ) - 1

여기서 $M = 2^P - 1$ 이고, $q_1 \le q_2 \le \dots \le q_m$ 은 $M$ 의 소인수를 오름차순으로 나열한 것이다. 같은 소인수가 $M$ 을 여러 번 나누면 나누는 횟수만큼 반복해서 쓴다. 기호 사이의 공백도 위 형식 그대로 지킨다.

메르센 합성수 자체가 작은 것부터 출력한다. 조건을 만족하는 수가 없으면 아무것도 출력하지 않는다.

예제 1

입력

예상 출력

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