글 읽기 - C++ 시간 초과 ㅠㅠㅠ

husy951 6년 전 0

어떠한 문제일까요..? 에라토스테네스 체를 구현한 방법이 잘못된건가요..?

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

int main()
{
	int num1, num2;
	vector <int> park;
	cin >> num1 >> num2;

	for (int i = num1; i <= num2; i++) {
		park.push_back(i);
	}
	for (int j = 2; j <= num2;j++){

		for (int k = 0; k < park.size();k++ ) {
			if (park[k] != 0 && park[k] >j) {
				if (park[k] != j && park[k] % j == 0) {
					park[k] = 0;
					
				}
			}
		}
		
	}
	for (int q = 0; q < park.size(); q++) {
		if (park[q] != 0) {
			cout << park[q] << "\n";
		}
	}
	
	return 0;
}

etaehyun4 6년 전 0

네 에라토스테네스 채 의미는 아시는 것 같은데 위와 같이 구현한 경우 후보군 전체를 다시 살펴보게 되고 % 연산으로 인해 속도가 매우 느려질 수 있습니다.

pseudocode는 wikipedia를 참고해보세요

husy951 6년 전 0

@etaehyun4

알려주신 내용 덕분에 소스 수정하여 맞았습니다 :) 감사합니다.

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

문제

문제

출처

ICPC

C++ 시간 초과 ㅠㅠㅠ

husy951 6년 전 0

etaehyun4 6년 전 0

husy951 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말