📝 12921 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

1. 문제 요약

• 1부터 입력받은 숫자 n 사이에 있느 소수의 개수 반환하는 함수 작성하기
• 소수 : 1과 자기 자신으로만 나누어지는 수

2. 접근방법

• boolean[] isPrime 배열 만들어서 각 수가 소수인지 아닌지 체크
  → 보통 소수 판별하는 메서드나 배열은 isPrime으로 변수 명명하기
• 처음에 2 이상 모든 수 소수라고 가정하고 시작하기
  → 0, 1은 소수가 아니기 때문이다
• 2 ~ 루트 n까지 돌면서 배수 제거하기
• 최종적으로 true로 남아 있는 수들을 카운트하면 그게 소수 개수

3. 정딥코드

class Solution {
    public int solution(int n) {
        
        boolean[] isPrime = new boolean[n + 1];
        
        // 처음에는 모두 true로 두고 0. 1은 소수가 아s니니까 제외
        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;
                }
            }
        }
        
        // 소수 개수 세기
        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) count++;
        }
        
        return count;
    }
}

에라토스테네스의 체에서 범위가 i*i <= n까지만 순회하면 되는 이유?

• 우리가 소수 판별을 할 때 i를 소수라고 가정하고 배수를 지워 나간다
• 여기까지만 검사하는 이유는 루트 n이후의 수는 이전 작은 소수들의 배수에서 다 걸러졌기 때문이다.

합성수의 특징

어떤 수 n이 합성수라면, n = a * b 꼴로 나타낼 수 있다. 이 때 a 와 b 중 적어도 하나는 루트 n 이하이다.

• 36 = 6 * 6
• 91 = 7 * 13
• 즉, 루트 n까지만 검사하면 모든 합성수의 약수 조합을 커버할 수 있다.

(int j = i * i; j <= n; j += i 에서 i*i 부터 검사하는 이유

• i * i는 n의 제곱근을 의미한다.
• 그리고 i * i 이상부터가 아직 안 지워진 새로운 배수이기 때문이다.
• 이렇게 하면 중복 연산을 줄일 수 있다.

예를 들면, n = 30일 때

• i = 2라면 4, 6, 8, ... , 30 지워짐
• i = 3일때 9, 12, 15, ..., 30 지워짐

만약에 여기서 i=6 부터 시작하면

이미 6의 배수는 앞에서 다 지워짐 12, 18, 24, 30은 다 지워졌기 때문에

따라서 i = 6이후로는 새롭게 지울 게 없다 그래서 i * i 부터 지우면 된다.