섹션 2. Array - 5. 소수(에라토스테네스 체)

📌 문제 설명

자연수 N이 입력되면 1부터 N까지의 소수의 개수를 출력하는 프로그램을 작성하세요.

예를 들어, 20이 입력되면 1부터 20까지의 소수는 2, 3, 5, 7, 11, 13, 17, 19로 총 8개입니다.

---

📝 입력 & 출력

입력

• 첫 줄에 자연수의 개수 N(2 ≤ N ≤ 200,000)이 주어집니다.

출력

• 첫 줄에 소수의 개수를 출력합니다.

---

🔸 예제 입력 & 출력

예제 입력 1

20

예제 출력 1

8

---

💡 해결 방법

1. 에라토스테네스의 체 알고리즘을 사용하여 1부터 N까지의 소수를 찾습니다.
2. 배열을 이용하여 소수가 아닌 숫자들을 체크합니다.
3. 체크되지 않은 숫자(소수)의 개수를 카운트하여 출력합니다.

---

💻 코드 구현 (Java)

package partArray;

import java.util.*;

public class Problem5 {
	public int solution(int n){
		int count = 0;
		int[] arr = new int[n+1];
		
		for(int i=2; i<=n; i++) {
			if(arr[i]==0) {
				count++;
				for(int j=i; j<=n; j=j+i) arr[j]=1;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Problem5 T = new Problem5();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		System.out.print(T.solution(n));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 배열 초기화

int[] arr = new int[n+1];

• 배열을 이용하여 소수가 아닌 숫자를 체크합니다. 초기 값은 모두 0으로 초기화됩니다.

2️⃣ 에라토스테네스의 체 알고리즘 적용

for(int i=2; i<=n; i++) {
	if(arr[i]==0) {
		count++;
		for(int j=i; j<=n; j=j+i) arr[j]=1; // i의 배수는 모두 소수 아님
	}
}

 

• i = 2부터 n까지 순회
• arr[i] == 0이면 → 아직 체크되지 않은 수 → 소수
• 소수로 확정 → count++
• 그 다음 i의 배수들을 모두 1로 표시 (소수가 아님으로 마킹)

 

---

⏳ 시간 복잡도 분석

• 에라토스테네스의 체 알고리즘의 시간 복잡도는 약 O(N log log N)입니다.

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런