Lv.1 : 소수 찾기

👉 문제링크

프로그래머스

---

 

---

🔸 문제 분석 🔸

• 1부터 주어진 수 사이의 소수의 개수를 반환한다.

🔸 코드 🔸

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

        for(int i = 2; i <= n; i++){ // 소수 찾기
            if(prime[i] == 0) {
                int j = 1;
                while (i * ++j <= n) {
                    prime[i * j] = 1;
                }
                answer++;
            }
        }
        return answer;
    }
}

🔸 코드 해석 🔸

• 1은 소수가 아니니 제외하고, 1부터 n까지 i를 늘려가며 소수인지 판별한다.
  • n크기로 만든 prime 배열의 값이 0이면 소수라는 것이다.
  • prime 배열에서 i의 배수들은 소수가 아니므로 1을 넣어준다.
  • 0 값만큼 소수의 개수를 센다.

---

🔸 end 🔸

• 나눠지는 수를 찾으면 반복 횟수가 많아지므로 배열에서 배수를 제외하는 식으로 점차 리스트에서 소수가 아닌 수를 제외하는 방식으로 진행한다.
• 지금 보니 prime 배열은 int형 배열이 아니라 boolean형으로 했으면 좋았을 것 같다.
• 이전에 풀어봤던 문제인데 문제점을 조금 개선했다.
  • prime의 값에 1~n값을 넣어주고 마지막에 0이 아닌 값드의 개수를 셌는데, 개선해서 인덱스 i로 간단히 계산했다.