[프로그래머스] LV.1 소수 찾기 - Java [56/80]

💬 문제 설명

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

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

 

🚫 제한 사항

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

 

📢 입출력 예

 

👨‍🏫 입출력 예 설명

 

📃 제출 코드

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;
    }
}

 

✏ 해결방법 & 배운점

1은 소수가 아니기 때문에 반복문을 2부터 `n`까지 돌렸습니다. 이때, 각 숫자가 소수인지 확인하기 위해 `isPrime`이라는 boolean 변수를 선언했습니다.

 

이중 for문을 사용하여, `i`가 소수인지 확인했습니다. 내부 for문은 2부터 `i`의 제곱근까지 반복하며, `i`가 `j`로 나누어 떨어지는지 검사합니다. 만약 `i`가 `j`로 나누어 떨어진다면, `i`는 소수가 아니므로 `isPrime`을 false로 설정하고 내부 for문을 종료합니다.

 

내부 for문이 종료된 후,`isPrime`이 여전히 true라면 `i`는 소수이므로 `answer`를 1 증가시킵니다.

최종적으로, answer는 2부터 n까지의 소수 개수를 반환합니다.