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

문제 설명

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

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

제한 조건

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

입출력 예

n	result
10	4
5	3

풀이

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

우선 1은 소수에서 제외하니까 2부터 n까지 순회하면서 각각 소수인지 확인한다.

for(int i = 2; i<= n; i++) { }

소수 판별은 2부터 해당 수의 √i까지 나누어 떨어지는 수가 있는지 확인한다.

for(int j = 2; j * j <= i; j++) {
	if(i % j == 0) { }
}

만약 소수일 경우 정답에 카운트를 추가하였다.

if(check) {
	answer++;
}