[프로그래머스/135808] 소수 찾기

04 Jan 2025 in Study / Coding Test

• ☑️ 문제
• ☑️ 풀이
  • 효율성 통과 X
  • 효율성 통과 O

☑️ 문제

프로그래머스 135808

☑️ 풀이

효율성 통과 X

import java.math.*;

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

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

            if (isPrime) {
                answer++;
            }
        }

        return answer;
    }
}

효율성 통과 O

• 검색해보니 에라토스테네스의 체를 사용하여 풀어야 한다.
• 에라토스테네스의 체는 2부터 시작하여 배수들을 제거하는 방식으로 소수를 찾는 알고리즘이다.
  • 기존에는 배수를 모두 체크해줘서 효율성 테스트를 통과하지 못한 것 같다.
  • 배수는 소수가 아니기 때문에 미리 제거한 후에 소수를 카운팅하면 된다.

import java.math.*;

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] isPrime = new boolean[n + 1];

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

        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (isPrime[i]) {
                for (int j = i * i; j <= n; j+=i) {
                    isPrime[j] = false;
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                answer++;
            }
        }

        return answer;
    }
}