글 읽기 - 소수 시간초과 질문입니다...

haung921209 6년 전 0

저는 store라는 크기 n+1짜리를 만들어놓고

index = 1일때는 1

2부터는 소수인 경우는 제외, 그 소수의 배수의 경우 store배열값을 1로 하고

그 다음부터 배열값이 1인 경우는 패스하고 지나가게 되었습니다.

그런데 자꾸 시간초과가 나네요.....

이게 비효율적인 알고리즘인건가요?....ㅜ

#include<iostream>
using namespace std;

int main() {
	int m; int n;
	int result = 0;
	cin >> m >> n;

	int* store;
	store = (int*)malloc(sizeof(int)*(n+1));
	for (int i = 2; i <= n; i++)
	{
		store[i] = 0;
	}
	store[1] = 1;
	for (int i = 2; i <= n; i++) {
		if (store[i] == 0) {
			int k = 2;
			while (k*i <= n) {
				store[k*i] = 1;
				k++;
			}
		}

	}
	for (int i = m; i <= n; i++) {
		if(store[i]==0)
			cout << i << ::endl;
	}
	return 0;
}

zlzmsrhak 6년 전 2

출력할 때 endl을 자주 쓰는 것은 시간 효율이 매우 안좋습니다. 그래서 출력할 때는 endl 대신 "\n"을 사용하는 것이 좋습니다.

제가 알기로는 endl을 출력할 때 마다 버퍼를 비워주기 때문에 시간이 오래 걸리는 것으로 알고 있습니다.

haung921209 6년 전 0

바로 나오네요 감사합니다!

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

문제

문제

출처

ICPC

소수 시간초과 질문입니다...

haung921209 6년 전 0

zlzmsrhak 6년 전 2

haung921209 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말