[JAVA] 소수 찾기

문제설명

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

[제한 조건]
n은 2이상 1000000이하의 자연수입니다.

[입출력 예]

n        result
10        4
5        3

코드

int answer = 0;
        int number = n;
        int arr[] = new int[number+1];

        for(int i=2;i<=number;i++) {
            arr[i] = i;
        }

        for(int i=2;i<=number;i++) {
            if(arr[i]==0) continue; 

            for(int j=2*i;j<=number; j+=i) {
                arr[j] = 0;
            }
        }

        for(int i=2;i<=number;i++) {
            if(arr[i]!=0) {
                answer++;
            }
        }

        return answer;

• 찾아보니 에라토스테네스의 체를 사용해야 한다고 한다. 계산해야 하는 수까지의 배열을 만들어 준 후 곱한 값들은 지우고 남은 값만 계산 하였다.

1. 배열 생성
2. 소수가 아닌 1을 제외하고 2부터 시작하여 배수들을 모두 지운다.
3. 배열 안에 남아있는 수를 카운트한다.