[백준] 1929 소수 구하기 | 에라토스테네스의 채 | endl과 printf 속도 차이 | C++

C++

이 문제는 시간복잡도 때문에 여타의 소수 구하는 알고리즘과 다르게 풀어야한다.

이 문제는 '에라토스테네스의 채' 라는 알고리즘으로 해결 해야하고 해당 알고리즘 내용은 아래 위키백과에 잘 나와 있으니 한 번씩 보고 오도록 하자.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

전체 코드

//에라토스테네스의 채
#include <iostream>
#include <vector>
using namespace std;
void printPrime(int& idx1, int& idx2) {
	vector<bool> nums(idx2, true);
	for (int i{ 2 }; i <= idx2; i++) {
		if (nums[i - 1] == false)
			continue;
		/*
		i의 배수가 존재하면 false
		i의 배수의 개수 = idx2 / i
		*/
		for (int j{ 2 }; j <= idx2 / i; j++)
			nums[i * j - 1] = false;
	}
	for (int i{ idx1 }; i <= idx2; i++)
		if (nums[i - 1])
			cout << i << "\n"; //endl 사용하면 시간초과. 반드시 "\n" 사용.
}
int main(void) {
	int idx1, idx2;
	cin >> idx1 >> idx2;
	//1은 소수도 합성수도 아니다.
	if (idx1 == 1)
		printPrime(++idx1, idx2);
	else
		printPrime(idx1, idx2);
	return 0;
}

코드 해설

vector<bool> nums(idx2, true);

소수를 판별하고 소수가 아닌 수이면 false를 저장할 벡터 nums를 선언한다. 기본값은 true이며, 이후 true는 소수를 의미한다.

for (int i{ 2 }; i <= idx2; i++) {
	if (nums[i - 1] == false)
		continue;
	/*
	i의 배수가 존재하면 false
	i의 배수의 개수 = idx2 / i
	*/
	for (int j{ 2 }; j <= idx2 / i; j++)
		nums[i * j - 1] = false;
}

for 반복문은 숫자 2부터 idx2까지 실행된다.

먼저, nums 배열 요소 값이 false이면 이미 소수가 아닌 수라서 넘어가게 된다.

아래 코드가 중요한데, for문의 조건식을 보면 idx2 / i 라는게 적혀 있을 것이다. 이는, 만약에 idx2에 대해 i의 값이 2개 이상의 배수가 존재하면 그 수는 소수가 아닌 합성수라서 nums배열에서 false 처리 해야할 것이다. 

이때, i의 배수의 개수가 2개 이상인 이유는 i는 소수이기 때문에 배제 해야한다.

for (int i{ idx1 }; i <= idx2; i++)
	if (nums[i - 1])
		cout << i << "\n"; //endl 사용하면 시간초과. 반드시 "\n" 사용.

idx1부터 idx2까지 범위에서 nums 배열 요소가 true면 소수이므로 출력을 진행하게 된다.

이때, 주의해야할 점은 출력문에서 endl를 사용하게 되면 시간초과가 발생하므로 반드시 "\n"을 사용해야 한다.

(endl과 "\n"의 속도 차이는 아래에서 별도로 설명한다.)

int main(void) {
	int idx1, idx2;
	cin >> idx1 >> idx2;
	//1은 소수도 합성수도 아니다.
	if (idx1 == 1)
		printPrime(++idx1, idx2);
	else
		printPrime(idx1, idx2);
	return 0;
}

main함수 코드에서 주목할 부분은 idx1가 1이면 printPrime함수 인수 전달시 1 증가시켜서 보낸다.

그 이유는 1은 소수도 합성수도 아니기에 만약에 1을 그대로 인수 전달시 printPrime함수 출력에 영향이 미치게 된다.

---

번외 : endl과 "\n"과 printf함수 속도 차이

이 문제의 출력문을 endl로 바꾸면 시간 초과가 발생할 것이다.

이는 endl과 "\n"의 속도 차이에서 발생하는 건데 아래 블로그 글을 보고 오면 도움이 될 것이다.

https://cocoon1787.tistory.com/135

[C/C++] endl 와 \n의 속도차이

전체 코드(반복문 범위 1,000,000 설정) 

#include<iostream>
#include<time.h>
using namespace std;

int main()
{
	clock_t start, end;
	double time1, time2, time3, time4;

	start = clock(); //시간 측정 시작

	// #time1 "cout << i << endl;"
	for (int i = 0; i < 1000000; i++)
	{
		cout << i << endl;
	}

	end = clock(); //시간 측정 끝
	time1 = end - start;


	// #time2 "cout << i << "\n";"
	start = clock(); //시간 측정 시작

	for (int i = 0; i < 1000000; i++)
	{
		cout << i << '\n';
	}

	end = clock(); //시간 측정 끝
	time2 = end - start;


	// #time3 "printf("%d\n", i);"
	start = clock(); //시간 측정 시작

	for (int i = 0; i < 1000000; i++)
	{
		printf("%d\n", i);
	}

	end = clock(); //시간 측정 끝
	time3 = end - start;

	printf("\n\n");
	cout << "cout << i << endl : " << time1 << "ms" << endl;
	cout << "cout << i << '\\n' : " << time2 << "ms" << endl;
	cout << "printf(\"%d\\n\", i) : " << time3 << "ms" << endl;
}

범위를 1,000,000으로 설정하면 필자 컴퓨터에서는 다음과 같은 성능을 보여준다.

위 코드와 출력문을 보면 속도면에서 printf 함수가 압도적임을 보여준다.

필자 컴퓨터가 평범한 보급형 노트북이기는 한데, 왠만해서는 printf를 아니면 "\n" 제어문자를 알고리즘 풀 때만 사용하도록 노력해보자!