글 읽기 - 소수 알고리즘에 제가 문제있는 것이 무엇일까요??

cooandc 7년 전 0

다른 방식으로 뺑뺑이 돌려서 푼 것은 맞았는데

제가 전에 다른 사이트에서는 이런 방식으로 풀어야 정답인 경우가 있어서(어디인지는 까먹었습니다 ㅜ)

이렇게 풀었더니 시간초과라고 뜨네요 ㅜ

일단 어거지로 풀고 다른 분들 푸는거 한 번 봤는데

이 코드와 별 차이도 못 느끼겠고.. 해서 질문 드립니다 ㅜ

#include <iostream>
#include <cmath>

using namespace std;

bool Prime[1000001];

int main()
{
	int M, N;

	cin >> M >> N;

	Prime[0] = Prime[1] = 1;

	for (int i = 2; i <= 1000; i++) {
		for (int j = i * i; j <= N; j = j + i)
			Prime[j] = 1;
	}

	for (int i = M; i <= N; i++)
		if (!Prime[i])
			cout << i << endl;

	return 0;
}

portableangel 7년 전 1

cout 대신 printf를 사용해 보세요

cooandc 7년 전 0

오 정말 printf를 쓰니까 바로 되네요!!

왜 그러는걸까요? ㅜ 차이점이 뭔지 모르겠습니다 ㅜㅜ

portableangel 7년 전 1

저도 항상 궁금합니다.

main 첫줄에 ios::sync_with_stdio(false); 를 불러주시고 scanf/printf 함수를 전혀 사용하지 않고 cin/cout으로만 코딩하시면 scanf/printf와 비슷한 속도가 나와요

아마 이걸로 추론해보면.. cin/cout은 모종의 동기화 과정이 있는게 아닐까 싶지만 뜯어본게 아니라 잘 모르겠네요

cooandc 7년 전 0

꽤 어려운 이유 같네요 ㅜ

답변해주셔서 정말로 감사합니다!!!

isangyoon 7년 전 1

몇 가지 이유들 때문에 std::cin, std::cout이 printf, scanf 보다 느립니다.

기본적으로, std::cin, std::cout은 C 라이브러리의 stdio 버퍼와 동기화하는데 시간을 소비하게 됩니다.

그래서 내부적으로 printf, scanf 과 혼합되어서 호출되기에 느려집니다.

윗분이 설명하셨듯, std::ios_base::sync_with_stdio(false) 등을 통해 동기화를 하는 것을 off 할 수 있고 속도를 향상시킬 수 있습니다.

두번째로, std::cout << std::endl 과 std::cout << '\n'의 차이 때문에 속도가 차이나게 됩니다.

전자 같은 경우 즉, std::endl은 강제적으로 flush하게 되는데, 이와 같은 작업이 필요하지 않아도 수행하게 되므로 std::cout << '\n'을 사용하시는 것을 권장합니다.

그 외에도 옛날 GCC 컴파일러에서는 버그가 있어서 iostream이 느리는 등의 이유가 있습니다.

결론적으로는 printf, scanf가 더 빠른편입니다. c++ 헤더 자체가 c의 헤더 보다도 무겁기도 하지요. (템플릿이라던지 더 복잡하게 짜여있기도 하구요)

대회를 준비하시는 입장이라면 특별한 문제가 되지 않으면 c++의 iostream을 활용하시되 std::endl 대신, '\n'와 동기화 과정을 꺼주시고 사용하시면 될 것이라 생각합니다.

그래도 TLE가 난다면 printf/scanf를 사용하시면 됩니다.

템플릿은 소스코드에 첨부했습니다.

#include <iostream>

int main(int argc, char** argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    
    // 코드 시작
    
    std::cout << answer << '\n';
    
    return 0;
}

cooandc 7년 전 0

정말로 감사합니다 많은 도움되었습니다

활동하면서 좋은 정보 많이 알아갑니다!!

감사합니다!!

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

문제

문제

출처

ICPC

소수 알고리즘에 제가 문제있는 것이 무엇일까요??

cooandc 7년 전 0

portableangel 7년 전 1

cooandc 7년 전 0

portableangel 7년 전 1

cooandc 7년 전 0

isangyoon 7년 전 1

cooandc 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말