백준 1929번 : 소수 구하기

문제 접근

---

1. 소수의 정의와 에라토스테네스의 체라는 개념이 떠올랐다.
   
     소수의 정의는 1과 자기 자신을 약수로 갖는 수. 에라토스테네스의 체란 작은 수부터 하나씩 확인하며 소수가 아닌 수를 소거해 가며 소수를 찾는 방법. 일단은 에라토스테네스의 체를 찾아보지 않고 구현해보려고 함.
   
   
2. 최악의 케이스를 상정해봤다.
   
     수 하나하나에 대해서 소수인지 아닌지 판별하려면 O(n^2)이 걸린다. 입력의 최댓값이 100만이기에, 최악의 경우, 1조 번 연산하게 되기에 단순하게는 풀지 못한다.
   
   
3. 결국 에라토스테네스의 체처럼 소수를 찾으려 하지 않고, 소수가 아닌 걸 거르는 방식으로 해결하고자 했다.
   
     Just do it!

 

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

1929번: 소수 구하기

 

 

 

문제 코드

---

#include <iostream>
#include <vector>

using namespace std;

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

	int M, N;
	vector<bool> prime_num(1000001, true);

	prime_num[1] = false;

	for (int divisor = 1; divisor < prime_num.size(); ++divisor)
	{
		if (!prime_num[divisor])
			continue;

		for (int dividend = divisor * 2; dividend < prime_num.size(); dividend += divisor)
			if (prime_num[dividend])
				prime_num[dividend] = false;
	}

	cin >> M >> N;

	for (int check_num = M; check_num <= N; ++check_num)
	{
		if (prime_num[check_num])
			cout << check_num << '\n';
	}

	return 0;
}

 

 

 

느낀 점

---

    기획 작업하면서 고민하고 글만 쓰다가, 간단하게라도 코딩하니까 사소한 것, 하나하나가 다 재밌당.

 

1. 입력과 시간제한으로 알고리즘을 유추해 보자.
   
     문제 내용 외에 입력 크기와 시간제한도 문제의 조건 중 하나다. 어느 정도 데이터가 쌓이면 이걸 바탕으로 알고리즘을 생각해 봐도 좋을 것 같다는 생각을 했다.
   
   
2. 알고리즘 문제이더라도 가능하면 변수 이름을 직관적으로 지어보자.
   
     반복문에 i, j, k를 쓰는 것도 좋지만, 예전에도 그랬고, 내가 헷갈리는 경우들을 보면 각 변수가 어떤 역할을 하는지 정확히 정해놓지 않았기 때문이라는 생각이 들었다. 변수에 직관적인 이름을 짓는 연습은 실제 개발에서도 도움이 될 테니 되도록이면 직관적인 변수 명을 떠올리고 사용해 보자.
   
   
3. 풀이 방법이 잘 떠오르지 않으면 역으로 생각해 보자.
   
     에라토스테네스의 체가 '소수를 찾는다'보다는 '소수가 아닌 걸 소거한다'로 소수를 찾았던 것처럼 한 번씩 역으로 생각해 보도록 하자.