#Level 1 - 소수 찾기

[문제]

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

 

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

 

 

[다른 사람 풀이 참고]

이 문제는 내 풀이가 없고 다른 사람 풀이를 참고한 것만 있다.

 

알고리즘 문제 자체가 수학적 개념이 베이스가 된다고 생각을 하는데, 이번 문제와 같은 경우 특히나 소수의 개념과 특징을 얼마나 잘 아느냐에 따라 문제 풀이와 효율성이 달라질 것이라고 생각했다.

 

소수는 1과 자기 자신으로만 나누어지는 수, 다시 말해서 하나의 소수가 나오면 그 배수는 모두 소수가 아니기 때문에 범위 내에 이 조건에 해당하는 수들만 제외해도 답을 도출해 낼 수 있다는 것이다.

class Solution {
    public int solution(int n) {
        int answer = 0;
        boolean[] value = new boolean[n+1];

        for (int i=2;i<n;i++){
            value[i] = true;
        }
        int root = (int) Math.sqrt(n); //제곱근

        // 범위 내의 모든 수
        for (int i=2;i<=root;i++){
            // 소수 일 때
           if (value[i]){
               // 소수를 제외한 배수는 모두 소수가 아니다
               for (int j=i;i*j<=n;j++){
                   value[i*j] = false;
               }
           }
        }

        for (int i=2;i<n;i++){
            if (value[i]==true)
                answer++;
        }
        return answer;
    }
}

 

<문체 출처>

programmers.co.kr/learn/courses/30/lessons/12921?language=java

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