Codeforces Round #736 (Div. 2)-A. Gregor and Cryptography

문제 설명

조지는 RSA 암호화 방식을 공부하고 있다. 비록 조지는 RSA가 어떻게 작동되는지 모르지만 소수에 관심을 가지고 있고 그에 대한 인수에 매료되었다.

조지가 가장 좋아하는 소수는 $P$ 이다. 조지는 다음 속성을 모두 만족하는 두 정수를 찾고 있다.

• $P\;mod\;a = P\;mod\;b$
• $2 \le a < b \le P$

조지가 좋아하는 소수와 관련된 두 수를 찾아주자.

Input
첫번째 줄에는 테스트 케이스의 개수를 나타내는 정수 $t (1 \le t \le 1000)$ 이 주어진다.

각 테스트케이스의 첫번째 줄에는 소수 $P(5 \le P \le 10^9)$ 이 주어진다.

Output
각 줄마다 두 정수 $a, b (2 \le a < b \le P)$ 를 출력한다. 만약 답이 여러개 있다면 아무거나 출력한다.

Example
input
2
17
5

output
3 5
2 4

문제 접근

사용한 알고리즘: 정수론
걸린 시간 : 00:00:50
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이 문제를 B번 풀고와서 겨우 풀었다니 나는 이런 단순한 수학 문제를 아주 싫어한다. 다음부터는 이런 문제 나와서 10분안에 못풀면 그냥 그 virtual contest 포기해야겠다.

주어진 소수가 5보다 크기 때문에 이 소수는 반드시 홀수이다. 즉 소수 2를 약수로 가지지 않는다. 그러면 반드시 2로 나눈 나머지 값은 1이다. $P\;mod\;a = 1$ 을 만들 수 있는 가장 쉬운 $a$는 그냥 $P-1$ 이기 때문에 그냥 이 두 수를 출력하면 된다.

정답 코드

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        cout << 2 << " " << n - 1 << "\n";
    }
    return 0;
}