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

문제 설명 :

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

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

 

제한 조건 : 

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

입출력 예 :

n	result
10	4
5	3

입출력 예 설명 : 

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

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

 

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

알고리즘 설명 :

1. 1과 n 사이의 소수 개수를 반환할 객체 answer를 생성하고 0으로 초기화

2. 1은 소수가 아니기에 for 문에서 1이 아니라 2부터 시작

3. 소수는 1과 자기 자신으로만 나눠지므로 자기 자신으로 한번 나눠질 때만 소수로 판별

4. test가 true 일때만 answer을 1씩 증가

5. return을 사용하여 answer을 반환