(프로그래머스)소수찾기 - P12921

문제설명

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

 

제한조건

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

입출력 예

n	result
10	4
5	3

 

---

코드설명

이 소수 찾기 문제는 에라토스테네스의 체를 사용하여 문제를 풀면 쉽게 풀 수 있다.

 

소수를 판별하기 위해 boolean배열을 만든다.

0과 1은 소수가 아니므로 true로 초기화해준다.

boolean[] prime = new boolean[n + 1];

prime[0] = prime[1] = true;

 

for문을 사용해 prime의 길이의 제곱근만큼 반복문을 실행한다.

for (int i = 2; i <= Math.sqrt(prime.length); i++) {

}

 

이미 체크된 배열이면 다음 반복문으로 스킵해준다.

if(prime[i]) continue;

 

아래 코드의 의미는 i의 배수들을 걸러주기 위한 반복문이다.

true는 소수가 아니고, false는 소수이다.

for (int j = i * i; j < prime.length; j += i) {
    prime[j] = true;
}

 

이 반복문이 끝나면 prime배열에 false인 것만 answer을 증가시켜준다.

for (int i = 0; i < prime.length; i++) {
    if (!prime[i]) {
    answer++;
    }
}

 

---

코드

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

        prime[0] = prime[1] = true;

        for (int i = 2; i <= Math.sqrt(prime.length); i++) {
            if (prime[i]) {
                continue;
            }
            for (int j = i * i; j < prime.length; j += i) {
                prime[j] = true;
            }
        }

        for (int i = 0; i < prime.length; i++) {
            if (!prime[i]) {
                answer++;
            }
        }

        return answer;
    }
}

 

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges