프로그래머스 레벨 1 - 소수 찾기

코딩테스트 연습 - 소수 찾기

문제 설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.(1은 소수가 아닙니다.)

---

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

---

입출력 예

n	result
10	4
5	3

입출력 예 설명

입출력 예 #11부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

입출력 예 #21부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

---

풀이

class Solution {
    public int solution(int n) {
        int answer = 0;
        for (int i = 2; i <= n; i++) {
            boolean isPrime = true;
            for (int j = 2; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) answer++;
        }
        return answer;
    }
}

리뷰

• 소수를 찾는 문제는 에라토스테네스의 체 또는 제곱근을 구하는 것으로 품.
• 주어진 수 N의 제곱근 범위 안에서 소수 판별하는 법
  • N의 약수는 무조건 N의 제곱근 범위 안에 존재.
    • 예) N = 36
    1. 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
    2. $36 = 1 * 36$ / $2 * 18$ / $3 * 12$ / $4 * 9$ / $6 * 6$ / …
    3. $36 = 1 * 2^2 * 3^2$
    • 결국 N은 제곱근인 6의 약수로 이루어져 있음.
    • 따라서 N의 제곱근까지만 판별하면 됨.