[인프런] 02_05 소수 (에라토스테네스 체)

📖 문제

---

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

출력화면

 

✍️ 이해

---

• 우선 "에라토스테네스 체"가 무엇인지부터 알아야 할 것 같다. 에라토스테네스 체란?

출처) 위키백과

• 2부터 소수를 구하고자 하는 구간의 모든 수(N)를 나열한다. 그림에서 회색 사각형들이 여기에 해당한다.
• 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
  • 자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
  • 자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
  • 자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
  • 자기 자신을 제외한 7의 배수를 모두 지운다.
• 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

 

⚠️ 주의사항

---

• 에라토스테네스의 체 사용해서 풀어보기.

 

✏️ 풀이

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 에라토스테네스 체
 */
public class Java_02_05 {

    public int solution(int n) {

        int answer = 0;
        int[] ch = new int[n + 1];

        for (int i = 2; i <= n; i++) {
            if (ch[i] == 0) {
                answer ++;
                for (int j = i; j <= n; j=j+i) { // j가 i의 배수만큼 증가해야 하므로 j = j + i;
                    ch[j] = 1;
                }
            }
        }
        return answer;
    }

    public static void main(String[] args) throws IOException {

        Java_02_05 T = new Java_02_05();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        System.out.println(T.solution(N));
    }
}