글 읽기 - 시간초과가 왜 날까요..?

cleankid99 5년 전 1

에라토스테네스의 체를 쓰지않고 풀려고했거든요

비주얼스튜디오상에서도 123456을 입력해서 풀어도 바로 값이 나오는데

20%에서 바로 시간초과가 뜨네요..

개선할 점이 있을까요?

#include <iostream>
using namespace std;

int main() {
	long long n, test, result=0, i, j;
	while (1) {
		cin >> test;
		if (test == 0) { return 0; }
		for (i = test+1; i <= 2 * test; i++) {
				for (j = 2; j*j <= i; j++) {
					if (i%j == 0) { result--; break; }
				}
				result++;
		}
		cout << result << '\n';
		result = 0;
	}
	return 0;
}

jh05013 5년 전 1

123456이 20개 정도 들어오면 시간초과입니다.

cleankid99 5년 전 1

이렇게 수정해서 풀었더니 통과했어요 감사합니다~

#include <iostream>
using namespace std;

int main() {
	long long n, test, result=0, i, j;
	while (1) {
		cin >> test;
		if (test == 0) { return 0; }
		else if (test == 1) { cout << 1 << '\n';}
		else {
			for (i = test + 1; i <= 2 * test; i++) {
				if (i % 2 != 0) {
					for (j = 3; j*j <= i; j += 2) {
						if (i%j == 0) { result--; break; }
					}
					result++;
				}
			}
			cout << result << '\n';
			result = 0;
		}		
	}
	return 0;
}

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

문제

문제

출처

ICPC

시간초과가 왜 날까요..?

cleankid99 5년 전 1

jh05013 5년 전 1

cleankid99 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말