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

프로그래머스 Lv1 - 소수 찾기 문제

프로그래머스 코딩테스트 문제 중 레벨 1 소수 찾기 문제를 풀이했다.
지난번에 공부했던 소수 찾기 알고리즘 방법 중 하나인 에라토스테네스의 체 알고리즘을 잊지 않기 위해 요즘 코딩 테스트 문제 중 소수 관련 문제가 나오면 항상 풀어보는 편이다. 문제 제목대로 주어진 1 ~ n 범위내에 있는 소수만을 찾는 문제라 2분(코드 작성 시간)만에 바로 풀었다.

FindPrimeNum.java

package com.example.Programmers.Lv1;

/**
 * 프로그래머스 Lv1 - 소수 찾기 문제
 * 에라토스테네스의 체 알고리즘으로 풀이
 */
public class FindPrimeNum {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n + 1];

        // 소수 배열 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        // 소수가 아닌 수에 0 삽입
        for (int i = 2; i <= Math.sqrt(arr.length); i++) {
            if (arr[i] == 0) {
                continue;
            }
            for (int j = i + i; j < arr.length; j = j + i) {
                arr[j] = 0;
            }
        }

        // 소수이면(배열의 요소가 0이 아니면) 정답 변수에 +1
        for (int i = 2; i < arr.length; i++) {
            if (arr[i] != 0) {
                answer++;
            }
        }
        return answer;
    }
}

FindPrimeNumTest.java

package com.example.Programmers.Lv1;

import static org.junit.Assert.assertEquals;

import org.junit.Test;

public class FindPrimeNumTest {
    @Test
    public void testFindPrimeNum() {
        FindPrimeNum f = new FindPrimeNum();

        int result1 = f.solution(10);
        int result2 = f.solution(5);

        assertEquals(4, result1);
        assertEquals(3, result2);
    }
}