글 읽기 - 시간초과가 나는데 어디서 시간을 줄여야할까요?!

dhworhkd11 4년 전 0

에라토스체 외에는 for문 중첩도 없는데 시간을 어디서 절약시켜야 할까요?!

#include <iostream>
using namespace std;
const int MAX = 100000;
bool check[MAX + 1] = { false };
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	check[0] = true;
	check[1] = true;
	for (int i = 2; i <= MAX; i++)
	{
		if (check[i] == false)
		{
			for (int j = i * 2; j <= MAX; j += i)
				check[j] = true;
		}
	}
	while (true)
	{
		int n;
		cin >> n;
		if (n == 0)
		{
			break;
		}

		int max = 0;
		int left = 0, right = 0;
		for (int i = 3; i < n; i++)
		{
			if (check[i] == false && check[n - i] == false)
			{
				int di = (n - i) - i;
				max = max >= di ? max : di;
				if (max == di)
				{
					left = i;
					right = n - i;
				}
			}
		}
		if (max == 0)
			cout << "Goldbach's conjecture is wrong.\n";
		else
			cout << n << " = " << left << " + " << right << '\n';
	}
	return 0;
}

djm03178 4년 전 0

https://www.acmicpc.net/board/view/44906

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

문제

문제

출처

ICPC

시간초과가 나는데 어디서 시간을 줄여야할까요?!

dhworhkd11 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말