[백준] 11502-세 개의 소수 문제(C++)

문제링크:https://www.acmicpc.net/problem/11502

11502번: 세 개의 소수 문제

 

에라토스테네스의 체 알고리즘을 알고있어야합니다.

아래코드입니다.

for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	

소수의 배수는 소수가 아닌 것을 이용해서 소수에는 0 비소수에는 1을 넣어놓습니다. 

 

그이후 O(n^3)만큼 삼중포문으로 반복하면서 값을 판별해주는 완전탐색문제 (브루트 포스) 였습니다. 

 

구현이 너무 쉽기때문에  나머지 설명은 생략하겠습니다.

 

정답코드입니다. 

#include <iostream>
using namespace std;
int t = 0, n = 0;
int arr[1001] = { 0 };


int main() {
	for (int i = 2; i <= 1000; i++) {
		if (arr[i] == 1) continue;
		for (int j = i + i; j <= 1000; j += i)
			arr[j] = 1;
	}
	
	cin >> t;
	while (t--) {
		bool jud = false;
		cin >> n;
		for (int i = 2; i <= n; i++) {
			if (arr[i] == 1) continue;
			for (int j = 2; j <= n; j++) {
				if (arr[j] == 1) continue;
				for (int k = 2; k <= n; k++) {
					if (arr[k] == 1) continue;

					if ((i + j + k) == n) {
						cout << i << ' ' << j << ' ' << k << endl;
						jud = true;
						break;
					}
				}
				if (jud == true)
					break;
			}
			if (jud == true)
				break;
		}
	
	}
}