문제
메르센은 16세기 유명한 학자이다.
음악, 철학, 수학등 다양한 분야에서 활동 하였으며, 수학사에서는 ‘메르센의 수’를 발견한 것으로 유명하다.
메르센은 다음과 같은 가설을 정의하였다. ‘임의의 정수 N이 소수일 경우 2N-1의 수 역시 소수이다.’ 예전의 경우 컴퓨터도 없는 시절이었기에 이것이 맞을 것이라 생각하는 사람이 대부분이었으나, 기술의 발달로 인하여 이 가설은 참이 아니라는 것을 알게 되었다.
허나 메르센의 많은 위대한 업적을 기리기 위해서 메르센의 가설 중 참이 되는 숫자를 ‘메르센의 소수‘라고 이름 지었다.
메르센의 소수의 예는 다음과 같다.
지금부터, 메르센의 가설에 어긋나는 숫자들을 찾아보자.
다시 말해서 N이 소수이면서 2N-1이 합성수인 수를 찾는 것이다.
입력
첫 번째 줄에 1이상 59이하의 정수 N이 주어진다.
출력
N이하의 메르센의 가설에 어긋나는 숫자를 아래와 같은 형식(공백으로 구분)으로 출력한다.
첫 번째 부분은 2N-1을 소인수분해 한 결과이고, 그 다음에는 2N-1을 계산한 결과이다.
조건을 만족하는 숫자가 없을 경우는 "NONE!"이라고 출력한다.
예제
31
23 * 89 = 2047 = ( 2 ^ 11 ) - 1
47 * 178481 = 8388607 = ( 2 ^ 23 ) - 1
233 * 1103 * 2089 = 536870911 = ( 2 ^ 29 ) - 1
출처
Pacific Northwest 2004, poj 2191
로그인해야 코드를 작성할 수 있어요.