[Java] 2023_0723 소수 찾기

7/19 코딩테스트

---

문제 설명

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

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

풀이(오류)

class Solution {
    public int solution(int n) {
        int cnt=1;
        for(int i=3; i<=n; i++){
            for(int j=2; j<i; j++){
                if(i%j==0){
                    cnt++;
                    break;
                }
            }
        }
        int answer=n-cnt;
        return answer;
    }
}

효율성 테스트에서 문제가 생겨버렸다. 다른 사람들의 풀이를 보니 에라토스테네스의 체를 사용하지 않으면 효율성 테스트에서 실패가 뜨는 것 같다.

풀이

class Solution {
    public int solution(int n) {
        int answer=0;
        boolean prime[]=new boolean[n+1];
        for(int i=2; i<=n; i++){
            prime[i]=true;
        }
        int root=(int)Math.sqrt(n);
        for(int i=2; i<=root; i++){
            if(prime[i]==true){
                for(int j=i; j*i<=n; j++){
                    prime[i*j]=false;
                }
            }
        }
        for(int i=2; i<=n; i++){
            if(prime[i]==true){
                answer++;
            }
        }
        return answer;
    }
}

에라토스테네스의 체란?

• 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
• 2는 소수이므로 오른쪽에 2를 쓴다.
• 자기 자신을 제외한 2의 배수를 모두 지운다.
• 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다.
• 자기 자신을 제외한 3의 배수를 모두 지운다.
• 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다.
• 자기 자신을 제외한 5의 배수를 모두 지운다.
• 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다.
• 자기 자신을 제외한 7의 배수를 모두 지운다.
• 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다.

---

이러한 알고리즘을 에라토스테네스의 체라고 한다..는것 같다. 아무튼 이 알고리즘을 이용하여 풀면
prime을 n+1 크기를 주어주고 2~n까지를 true로 초기화해주었다. i는 n제곱근보다 작거나 같을 때까지 반복한 후 에라토스테네스의 체에 따라 i*j에 해당하는 prime인덱스를 모두 false로 바꾼다. 여기서 prime의 true만 소수이므로 prime을 반복시켜 true의 갯수를 구하여 소수를 찾을 수 있다