[프로그래머스, JAVA, Lv1] 소수 찾기

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

프로그래머스

 

<문제 설명>

 

<문제 해석1>

1. 1부터 n사이 수를 확인한다. (단, 1은 소수X)
2. 소수인지 체크 후 카운트한다.

 

<문제 풀이1> - 효율성 X

class Solution {
    public int solution(int n) {
        int answer = 0; // 소수의 개수
        // 1. for(1~n까지 소수체크) 
        for(int i=2; i <= n; i++){
            // 2. if(소수일 경우) answer++
            if(isPrime(i)) answer++;
        }
        
        return answer;
    }
    
    // 소수 체크 메서드
    public boolean isPrime(int num){
        boolean check = true;
        for(int i = 2; i <= Math.sqrt(num); i++){
            if(num % i == 0) check = false;
        }
        
        return check;
    }
}

 

효율성테스트가 다 실패했다. 

이유는 일부 배수들을 일일이 다 체크해서 그런 것 같다.

배수들을 제거해주면 될 듯 하다.

 

 

<문제 해석2>

1. 1부터 n사이 수를 확인한다. (단, 1은 소수X)

1-1. OO의 배수를 제거해준다. 배수는 소수가 아니므로.

1-2. 에라토스테네스의 체는 2부터 시작하여 배수들을 제거하는 방식으로 소수를 찾는 알고리즘
2. 소수인지 체크 후 카운트한다.

 

<문제 풀이2>

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

        // 초기화: 2부터 n까지 모든 숫자를 소수로 가정
        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;
    }
}

수정 후 통과했다 v