프로그래머스 소수 찾기 자바

문제

풀이

1. 처음 풀이(시간초과)

    // 내 풀이(시간 초과)
     public int solution(int n) {
         int answer = 0;
         for(int i = 2; i <= n; i++){
             boolean chk = true;
             for(int y = 2; y <= i/2; y++){
                 if(i%y==0){
                     chk=false;
                     break;
                 }
             }
             if(chk){
                 answer++;
             }
         }
         return answer;
     }

2. 에라스토테네스의 체

    // 에라스토테네스의 체
    public int solution2(int n) {
        int answer = 0;
        // 주어진 수를 담을 배열을 생성
        int[] arr = new int[n+1];
        // 배열을 각 인덱스의 수로 초기화
        for(int i = 1; i <= n; i++){
            arr[i] = i;
        }
        // 처음 소수인 2부터 시작
        for(int i = 2; i <= n; i++){
            // 현재 인덱스 번호와 실제 값이 일치하면
            if(arr[i] == i){
                // 해당 숫자의 배수는 소수가 아니므로 0으로 수정
                for(int j = i + i; j <= n; j += i){
                    arr[j] = 0;
                }
            }
        }

        // 처음 소수 2부터 n까지 인덱스와 실제 값이 일치하면 소수라는 뜻이므로 answer+1
        for(int i = 2; i <= n; i++){
            if(arr[i] == i){
                answer++;
            }
        }
        return answer;
    }

리뷰

에라스토테네스의 체를 사용해서 소수의 개수를 구하는 문제였다.

처음 풀이를 할 때 에라스토테네스의 체를 사용하지 않고 풀이를 했는데,
소수가 구해지긴 했지만 하나의 테스트 케이스에서 시간 초과가 발생하고 효율성 테스트를 통과하지 못했다.

알고보니 에라스토테네스의 체를 사용해야 하는 문제였다.

에라스토테네스의 체 구현 방법은

1. 주어진 수까지의 배열을 생성
2. 배열의 각 값을 인덱스 번호로 초기화
3. 첫번째 소수 2부터 구하고자 하는 수 n까지 반복을 진행
   • 이 때 각 수의 배수는 소수가 아니므로 배열의 값을 0으로 수정
4. 배열을 다시 2부터 n까지 탐색
   • 이 때 인덱스 번호와 배열의 수가 일치하는 경우만 소수이므로 이 경우에만 answer + 1