/ PRACTICE

Practice - 소수 찾기

programmers 바로가기

문제

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

입출력 예

n result
10 4
5 3

풀이1

효율성이 낮은 단점

class Solution {
    public int solution(int n) {
        int prime = 1;
        for(int i = 2; i < n+1; i++){
            if(i%2 != 0){
                int div = 0;
                for(int j = 1; j < i+1; j++){
                    if(i%j==0){
                        div++;
                    }
                }
                if(div == 2){
                    prime++;
                }
            }
        }
        return prime;
    }
}

풀이2

class Solution {
    public int solution(int n) {
        int prime = 1;
        for(int i = 2; i <= n; i++){
            if(i%2 != 0){
                int div = 0;
                for(int j = 1; j <= Math.sqrt(i); j++){ // 제곱근까지의 범위로 줄여내고
                    if(i%j==0){
                        div++;
                        if(div > 1){
                            break;  // 약수의 개수가 2개 이상이면 해당 수를 더이상 확인하지 않고
                        }
                    }
                }
                if(div == 1){
                    prime++;
                }
            }
        }
        return prime;
    }
}