[오늘의 문제] 소수 찾기

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

문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
n result
10 4
5 3
입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

내가 작성한 코드문

import java.util.*;
class Solution {
    public int solution(int n) {
        int answer = 0;
        
        // 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환
        
        for(int i = 1; i <= n; i++){   
            int count = 0; // 나눠지는 몫
            for(int j = 1; j <= n; j++){
                if(i % j == 0){// 나눠지면
                    count++; 
                }    
            }
            if(count == 2){
                answer++;
            }
        }
        
        return answer;
    }
}

채점 결과
정확성: 56.3
효율성: 0.0
합계: 56.3 / 100.0

56.3점이 뜬다.

시간초과 에러가 뜬다.

내부 루프가 j = 2부터 n까지 돌기 때문에, 전체 시간 복잡도는 O(n²) 수준.

이 방식은 n이 커질수록 극도로 비효율적이다.

예: n = 100,000이라면, 내부 반복문이 수십억 번 실행됩니다.

✅ 개선 방법: 에라토스테네스의 체 (Sieve of Eratosthenes)
1 ~ n 사이의 소수를 빠르게 구할 때 가장 널리 쓰이는 방법이다.

📌 핵심 아이디어:
소수의 배수는 모두 소수가 아님을 이용해 걸러냄

시간 복잡도: O(n log log n) (훨씬 빠름)

class Solution {
    public int solution(int n) {
        boolean[] isNotPrime = new boolean[n + 1]; // 기본값 false: 소수라고 가정, 0과 1은 소수가 아니기 때문에 미리 제외하는 코드
        isNotPrime[0] = true;// 0은 소수가 아닙니다.
그래서 **true로 설정해 "소수가 아니다"
        isNotPrime[1] = true;// 1도 소수가 아니다.

        for (int i = 2; i * i <= n; i++) {// 소수의 배수들을 지워주는 역할
            if (!isNotPrime[i]) {
                for (int j = i * i; j <= n; j += i) {// i는 현재 보고 있는 "소수 후보", i * i보다 작은 수의 배수들은 이미 더 작은 수에서 걸러졌기 때문, j는 i의 배수들, i가 소수일 경우, 그 배수들은 소수가 아니므로 제거
                    isNotPrime[j] = true;
                }
            }
        }

        int count = 0;
        for (int i = 2; i <= n; i++) {
            if (!isNotPrime[i]) count++;
        }

        return count;
    }
}

Math.sqrt()문을 사용한 방법

✅ 방법 설명: Math.sqrt()를 활용한 소수 판별
어떤 수 i가 소수인지 판별할 때, 2부터 √i까지만 나눠보면 충분하다.
왜냐하면 어떤 수가 소수가 아니라면, 반드시 √i 이하의 수로 나누어 떨어지기 때문이다.

class Solution {
    public int solution(int n) {
        int count = 0;

        for (int i = 2; i <= n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }

        return count;
    }

    private boolean isPrime(int num) {
        if (num < 2) return false;
        for (int i = 2; i <= (int)Math.sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
}