글 읽기 - 시간초과가 뜨는데 왜그런지 모르겠습니다.

wggwvs 1년 전 0

이 문제는 sqrt를 이용해도 풀리지 않는 문제인가요? 답은 얼추 맞는거 같은데, 계속 시간초과가 나옵니다. 그전까지 소수문제들은 sqrt를 이용해서 잘 풀었는데 이 문제는 sqrt를 이용해도 풀리지 않나요? 알려주세요..

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	int A = 1;
	int count = 0;
	int result = 0;
	while (1) {
		cin >> A;
		if (A == 0) { break; }
		int B = A * 2;
		if (A == 1 || A == 2 || A == 3 || A == 5) { cout << "1" << "\n"; }
		else if (A == 4 || A == 6 || A == 7) { cout << "2" << "\n"; }
		else if (A == 8) { cout << "3" << "\n"; }
		else {
			for (int x = A+1; x < B+1; x++) {
				int squre = sqrt(x);
				for (int i = 2; i < squre + 1; i++) {
					if (x % i == 0) { count++; }
				}
				if (count == 0) { result++; }
				count = 0;
			}
			cout << result << "\n";
		}
		result = 0;
	}
}

psj_0708 1년 전 3

같은 수에 대한 소수 판정이 여러 번 이루어지고 있기 때문입니다.

input으로 100000과 100001이 들어온다면

100001~200000 사이에 있는 자연수들이 모두 소수판정을 2번씩 받게 될테고, 각각은 O(n^(1/2))의 시간이 드므로 약 300~400번의 연산을 요합니다.

그러면 테스트케이스마다 3*10^7 번 이상의 연산을 새로 하고 있으니 시간 초과가 나겠죠?

문제의 핵심은 123456*2 까지 수를 먼저 소수 판정을 해놓고 테케마다 count만 하는 것입니다.

psj_0708 1년 전 1

그리고 19번 줄에서 i로 나누어떨어지면 이미 합성수이므로 break를 걸어주세요. 훨씬 시간이 절약될 겁니다.

wggwvs 1년 전 0

1. 위에 댓글은 에라토네스 체로 소수를 만들어놓고 각 테케마다 갯수만 세라는 말씀이신거 맞나요?

2. 합성수인데 계속 세는멍청한 짓을했네요... break거니까 바로 정답처리가 되네요

한수 가르쳐 주셔서 감사합니다.

psj_0708 1년 전 0

네 맞습니다!

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

문제

문제

출처

ICPC

시간초과가 뜨는데 왜그런지 모르겠습니다.

wggwvs 1년 전 0

psj_0708 1년 전 3

psj_0708 1년 전 1

wggwvs 1년 전 0

psj_0708 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말