글 읽기 - c코드 시간초과가 나오는데 이유가 궁금합니다.

yujong_lee 3년 전 0

채 이용해서 했는데 시간초과가 나는데

어떻게 고쳐야할지 모르겠습니다.

#define  _CRT_SECURE_NO_WARNINGS 
#include <cstdio>

int arr[1000001] = { -1 };
int main() {

	while (1) {
		int num;
		scanf("%d", &num);
		if (num == 0) break;
		for (int i = 2; i <= num; i++) {
			arr[i] = i;
		}

		for (int j = 2; j * j <= num; j++) {
			if (arr[j] == 0) continue;
			for (int k = j; k * j <= num; k++) {
				arr[j * k] = 0;
			}
		}

		for (int i = 2; i <= num; i++) {
			if (arr[i] != 0 && arr[num - i] != 0) {
				printf("%d = %d + %d", num, arr[i], arr[num - i]);
				break;
			}
		}
	}
}

ghghgh777 3년 전 1

arr를 n 값에 따라 새로 구할 필요가 없습니다.

yujong_lee 3년 전 0

malloc을 사용하지 않도록 수정을 했습니다만 여전히 시간초과가 나옵니다.

ghghgh777 3년 전 1

11-20번 줄이 while문 안에 있을 이유가 없다는 의미입니다. n이 100이든 1000이든 소수의 목록은 변하지 않으니 이를 while문 밖으로 빼내 한 번만 계산하도록 고치셔야 합니다.

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

문제

문제

출처

ICPC

c코드 시간초과가 나오는데 이유가 궁금합니다.

yujong_lee 3년 전 0

ghghgh777 3년 전 1

yujong_lee 3년 전 0

ghghgh777 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말