728x90
단계별로 풀어보기 - 수학 2단계 - [5단계] 9020번
문제
문제 링크 : www.acmicpc.net/problem/9020
입력 복사 :
3 8 10 16
CODE
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int i) {
int rt;
rt = sqrt(i);
if (rt == 1 && i != 1) { //2,3인 경우
return true;
}
if (i % 2) { //홀수일 경우
for (int j = 2; j <= rt; j++) {
if (!(i%j))
return false;
if (j == rt) {
return true;
}
}
}
}
int main() {
int T;
cin >> T;
for (int test_case = 0; test_case < T; test_case++) {
int n;
cin >> n;
for (int i = n / 2; i >= 2; i--) {
if (isPrime(i) && isPrime(n - i)) {
cout << i << " " << n - i << '\n';
break;
}
}
}
}
풀이
지난 소수 관련 문제와 동일한 방식을 이용하여 소수 여부를 리턴하는 isPrime함수를 만들었다.
두 수의 차이가 가장 작은 골드바흐 파티션을 구해야 하기 때문에,
n의 중앙값부터 2까지 감소시키며 두 수 모두 소수인지를 검사하였다.
결과
728x90
'Baekjoon > 단계별로 풀어보기' 카테고리의 다른 글
[BOJ / 백준] 3009번 네 번째 점 C++ 문제 풀이 (0) | 2020.11.11 |
---|---|
[BOJ / 백준] 1085번 직사각형에서 탈출 C++ 문제 풀이 (0) | 2020.11.11 |
[BOJ / 백준] 4948번 베르트랑 공준 C++ 문제 풀이 (0) | 2020.11.10 |
[BOJ / 백준] 1929번 소수 구하기 C++ 문제 풀이 (2) | 2020.11.10 |
[BOJ/백준] 2581번 소수 C++ 문제 풀이 (0) | 2020.11.10 |