BOJ 4948 베르트랑 공준

4948번: 베르트랑 공준

 

BOJ 상으로는 수학 카테고리에 있는데 이게 왜 수학 카테고리에 있는지는 모르겠는 문제, 에라토스테네스의 체를 쓸 수 있다면 매우 간단한 문제이다.

 

---

임의의 자연수 n ~ 2n 사이의 소수의 개수를 구하는 문제이다. 그런데 문제 하나에 1~123456 사이의 임의의 값이 입력되기도 하고, 한 번에 여러 개의 질문이 들어온다.

때문에 1~246912 사이의 모든 소수를 구해놓고, 구간 안에 들어있는 소수 개수를 세는 방식으로 해결한다.

 

알고리즘은 간단하다.

• 1 ~ 246912 사이의 소수를 모두 구해 리스트에 저장해둔다.
• 자연수 n이 입력되면 위의 리스트에서 n ~ 2n 사이의 소수 갯수를 카운팅해 출력한다.

그래서 에라토스테네스의 체 가 무엇인지, 왜 빠른지만 설명하고 넘어가고자 한다.

---

에라토스테네스의 체는 임의의 자연수 이하의 모든 소수를 구하려 할때 가장 빠르다고 알려진 방법이다.

인터넷에서는 임의의 수 1개가 소수인지를 판별하기에는 적합하지 않다고 하는데, 개인적인 생각으로 일반적인 상황에서는 충분하다고 생각한다. (애초에 에라토스테네스 체 시간 복잡도보다 빠르게 처리를 해야 하는 상황이면 논문 베이스로 구현을 하고 있지 않을까 싶다 ex 밀러라빈, aks)

 

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

위의 GIF가 에라토스테네스의 체 동작을 예쁘게 보여주는데, 동작 알고리즘도 간단하다.

• 리스트 내의 가장 작은 수를 꺼낸다. (꺼낸 수는 소수가 됨)
• 꺼낸 수의 배수들을 리스트에서 지운다.

이 두 가지 규칙을 원하는 자연수 N까지 반복하면 결국 1~N 사이의 모든 소수를 얻게 된다.

 

---

 

code

GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지