[백준] 2581:소수 (자바)

---

첫 시도는 실패했다.
출력 예시 값은 제대로 출력되었는데, 어떤 예외가 있는지 생각이 안난다..

---

지피티에 도움을 요청하니 만약 i 가 1일때의 경우를 생각하지 않아서였다.
i가 1이라면, ck 가 false가 되어 sum과 min에 값이 들어가게된다.
그래서 시작할 때 i가 1이라면 ck가 true가 되게 끔 설정해줬다.

---

하지만 소수를 찾는 방법이 굉장히 비효율적인 코드여서 공략의 힘을 빌렸다.
다른 사람들의 풀이와 지피티의 풀이도 에라토스테네스 체 알고리즘을 이용했다.

에라토스테네스 체 알고리즘

• 소수를 찾기 위한 고대 그리스 수학자 에라토스테네스가 고안한 알고리즘.
• 이 방법은 주어진 수 n 이하의 모든 소스를 빠르게 찾는 데 효율적이며, 간단하지만 강력한 소수 판별 방법으로 알려져 있다.

알고리즘 과정

1. 초기화 : 2부터 n까지 모든 수를 나열한다. 여기서 2는 소수임이 알려져 있음으로, 가장 처음 소수로 시작한다.
2. 소수 선택 : 가장 작은 소수 (처음엔 2)를 선택하고, 해당 소수의 배수를 모두 지운다. 이때, 자신은 지우지 않고 그대로 둔다.
3. 반복 : 다시 남아있는 수로 이동하여 소수로 판별하고, 그 소수의 배수를 다시 지운다.
4. 종료 조건 : $\sqrt n$ 보다 작은 수까지 확인이 끝나면 이후의 수들은 이미 소수로 판별된 상태가 된다.

에라토스테네스 체 알고리즘의 시간복잡도

• 주어진 범위 n에 대해 O($n\log\log{n}$)의 시간복잡도를 가진다.

알고리즘 구현 코드

boolean[] isPrime = new boolean[N+1];

for(int i = 2; i <= N; i++){
	isPrime[i] = true;
}

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

---

에라토스테네스 체 알고리즘을 적용시켜서 풀어보았다.

시간이 확실히 단축되었음을 확인할 수 있다.