시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 278 | 111 | 96 | 49.741% |
메르센 수는 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
ICPC > Regionals > North America > Pacific Northwest Regional > 2004 Pacific Northwest Region Programming Contest A번