[소수] 1929. 소수 구하기

1. 문제 해결 전략

앞서 설명한 에라토스테네스의 체 문제.. 근데 시간초과가  미친듯이 떴다.. 별에별짓을 다해봤는데 안되다가

다른 사람의 코드를 봤더니 cout<<endl말고 cout<<'\n'을 적용했더라. 혹시나 해서 이걸 바꿔봤더니 바로 통과 ㅋㅋ

궁금해서 구글링 해봤더니 endl은 내부 버퍼를 비워주는 역할까지 하기때문에 속도차이가 난다는 것.. 주의해야겠다.

 

아무튼.. 여기서 사용한 에라토스테네스의 체 코드는 어떤 수라도 그의 배수가 되는 값들은 절대 소수가 될 수 없다는 것이다. 1 뿐만아니라 그 수도 약수로 들어가기 때문에.. for문을 어떤식으로 구현할지는 자기각색이지만.. 2배수를 하던 자기자신을 곱해나가던 시간을 절반 이상으로 줄일수 있다는 것이 핵심이다!

 

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int M, N;
	cin >> M >> N;
	vector<bool> isprime(N + 1, true);

	isprime[0] = false;
	isprime[1] = false;

	for (int i = 2; i <= N; i++)
	{
		if (isprime[i])
		{
			for (int j = 2 * i; j <= N; j += i)
			{
				isprime[j] = false;
			}
		}
	}

	for (int i = M; i <= N; i++)
	{
		if (isprime[i])
			cout << i << endl;
	}
	return 0;
}

 

2. 걸린 시간

..

 

3. 느낀점

문제의 요지는 O(N)의 시간복잡도를 O(root(N))으로 만들라였는데.. 오히려 다른게 발목을 잡았다.

ps에서는 cin은 요긴해도 cout은 요긴하지 않은듯. 앞으로 개행은 endl 대신 '\n'을, 그리고 

 

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이것도 속도향상에 도움이 된다니깐 참고하자.

 

4. 링크

https://www.acmicpc.net/problem/1929