글 읽기 - 시간 초과가 납니다..

alswjd7461 3년 전 0

시간 초과가 어디에서 나는걸가요:ㅠ

#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int a[10001];

	int n;

	cin >> n;

	while (n) {
		int min = 9999;
		int b;
		cin >> b;

		a[0] = 0;
		a[1] = 0;

		for (int i = 2; i <= b; i++)
			a[i] = 1;

		for (int i = 2; i <= int(sqrt(b)); i++) {
			for (int j = 2; i * j <= b; j++) {
				a[i * j] = 0;

			}
		}

		int min1 = 0, min2 = 0;
		for (int m = b; m >= 2; m--) {
			for (int e = b; e >= 2; e--) {
				if (m + e == b && a[m] == 1 && a[e] == 1 && e <= m) {
					if (m - e < min) {
						min = m - e;
						min1 = m;
						min2 = e;


					}
				}

			}
		}
		cout << min2 << " " << min1 << '\n';
		n--;
	}

}

djm03178 3년 전 0

소수의 목록은 고정되어 있으므로 매 케이스마다 계산하는 대신 처음에 한 번만 계산해 두면 효율적입니다.

그리고 소수 쌍을 찾는 과정이 너무 비효율적입니다. 하나의 수를 고정하면 다른 하나의 수는 반복문을 돌리지 않아도 바로 알 수 있습니다. m + e == b이면 e = b - m일 테니 b부터 2까지 다 돌려볼 필요가 없습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간 초과가 납니다..

alswjd7461 3년 전 0

djm03178 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말