프로그래머스 Lv.1 - 소수 찾기

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

프로그래머스

 

1. 주어진 n을 가지고 n+1 크기를 가진 배열을 하나 생성한다.

2. 이 배열에는 0부터 n까지의 인덱스를 참조할 수 있는데 0을 제외한 인덱스 각각의 각 인덱스에 대한 약수의 수를 저장한다.

3. 해당 배열을 순회하면서 약수의 수가 2인 인덱스의 갯수를 구한다.

 

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] arr = new int[n+1];
 
        /* n + 1 크기를 가진 배열을 생성하고, 해당 배열 인덱스에 약수의 개수를 저장한다. */
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n/i; j++) {
                arr[i*j]++;
            }
        }
        /* 약수의 갯수가 2개인 수는 소수이므로 2개인 인덱스의 합을 구한다. */
        for(int i=0; i<arr.length; i++) {
            if(arr[i] == 2) answer++;
        }
        
        return answer;
    }
}