BOJ#1929 소수 구하기

BOJ#1929 소수 구하기

* 문제

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

* 풀이

- 단순히 접근하면, 체크하려는 모든 수 x에 대해 2부터 x까지 %연산을 해보는 방법이 있겠다. 그러나 주어진 숫자가 커질 수록 많은 시간이 걸리기 때문에 시간을 줄일 수 있는 방법을 생각해야 한다.

(정의) 소수 : 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수.

에라스토테네스의 체^[각주:1]

1. 2, 2를 제외한 모든 2의 배수를 제외한다.

2. 3, 3을 제외한 모든 3의 배수를 제외한다.

3. 4, 4를 제외한 모든 4의 배수를 제외한다.

...반복...

출처 및 공부 자료 : https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

※ 주의할 점

 - 1은 소수가 아니다. 

 - 테스트 케이스 구성 시 경계값에 유의한다.

M = Integer.parseInt(st.nextToken()); N = Integer.parseInt(st.nextToken()); primeNumArr = new int[N + 1]; for (int i = 0; i < N + 1; i++) { primeNumArr[i] = 1; } primeNumArr[1] = 0; for (int i = 2; i < N + 1; i++) { for (int j = 2; i * j <= N; j++) { primeNumArr[i * j] = 0; } } for (int i = M; i < N + 1; i++) { if (primeNumArr[i] == 1) { System.out.println(i); } }

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%231929_FindPrimeNumber

1. 가루, 물 등을 거르는데 쓰는 부엌 도구 [본문으로]