[백준(BOJ)]1929 - 소수 구하기 (C/C++)

백준 1929번 소수 구하기 문제. 단계 기본 수학2에 위치해 있다.

시간초과가 겁나 많이 떳다ㅠ 내 정답률을 얼마나 깎아먹었는지..

우선 시간초과가 개많이떳다

아무래도 2초라는 시간동안 100만의 숫자의 소수를 구해야하는데, 거기서 시간이 많이 걸린 것 같다.

해결법에는 ios_base::sync_with_stdio(false) << 를 사용했다

알고리즘에서 이 구문을 넣어주는 이유는 단순한데, 버퍼의 수를 줄여주기 때문에 실행 속도가 빨라지기 때문이다.

또한, C++에서 endl 대신 "\n"를 사용하여 더욱 시간을 줄여주었다.

결과는 성공!

ios_base와 관련되어 어떤식으로 동작하기에 버퍼수를 줄여주고 빨라지는 스택플로우에서 본 내용을 올리겠다..ㅎㅎ

https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull

 

해당 문제는 에라토스테네스의 체를 활용하여 풀었다.

에라토스테네스의 체는 소수를 찾을 때 활용하는 방법인데, 단순 노가다라고 생각해도 좋을 것 같다.

사실 소수에는 뭐랫지 일정한 패턴이 없댓나? 그렇기 때문에 노가다가 답이라고 들었던 것 같은데 기억이 안난다.

아무튼 잡담은 그만하고, 이걸 알려주자면

단순하게 숫자를 더해가며 배수들을 지우고, 남는 숫자들만 찍어내는 방법이다.

따라서 매우 큰 숫자가 된다면 연산이 많아져 힘들테고, 대충 100만 전후까지만 사용하는게 좋아보일 것 같다.

 

단순 for문으로 해결할 수 있는 문제이며, 어려웠던 이유는 시간초과와, 1을 예외처리 해주지 않았던 점? 이정도?

실버3치고는 약간 쉽게 나온 것 같지만, 에라토스테네스의 체를 모른다면 약간 헷갈렸을지도 모르는 문제라고 생각한다.

 

나무위키에도 친절하게 나와있는데, N이 N제곱근보다 크지않은...어쩌구저쩌구 인데 어려운건 넘어가도록 하겠다 ㅎㅎ;

#include <iostream>	
#define MAX 1000001
using namespace std;

bool check[MAX]{};

int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	fill_n(check, MAX, true);

	int a, b;
	cin >> a >> b;

	check[0] = false;
	check[1] = false;
	for (int i = 2; i <= b; i += 2)
	{
		if (i == 2) continue;
		check[i] = false;
	}
	for (int i = 3; i < b; ++i)
	{
		if (check[i] == true)
		{
			for (int j = i*2; j <= b; j += i)
			{
				check[j] = false;
			}
		}
	}
	for (int i = a; i < b+1; ++i)
	{
		if (check[i] == true)
			cout << i << "\n";
	}
}

check를 전부 false로 바꾸고 2만을 true로 해서 for문을 돌리는 방법으로 했다면, 첫 번째 for문을 안쓸 수 있었을텐데..

맞추고 나니까 생각이 들었다 ㅎㅎ,, 연산을 겁나 줄일 수 있었을텐데...

아무튼 진짜 3부터는 1씩 증가시키면서 check[i]가 true라면 배수 지워가면서 남은 true만 뽑아내었다.

풀고나니까 쉬워보였다는건 안비밀

 

다음 문제는 bfs나 dfs관련 문제를 풀어볼까 한다

이로서 내 105번째 문제 해결.

목표는 대학교 100등을 우선적으로 목표로 해볼 생각이다