소수의 개수 구하기

numberOfPrime 메소드는 정수 n을 매개변수로 입력받습니다.

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하도록 numberOfPrime 메소드를 만들어 보세요.

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

10을 입력받았다면, 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
5를 입력받았다면, 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

이 문제는

1. 1부터 n까지 각각 약수가 존재하는지 검사

2. 에라토스테네스의 체

이렇게 두가지 방법으로 풀 수 있다. 1번 방법은 모든 경우를 다 해보는 방법이고 2번 방법은 그나마 계산 수를 줄이는 방법이다. 그래서 2번을 선택했다.

class NumOfPrime {
    int numberOfPrime(int n) {
        int result = 0;
        int arr[] = new int[n+1];
 
        for(int i = 2; i < n+1 ; i++) {
            arr[i] = i;
        }
        
        for(int i = 2; i<n+1;i++) {
            if(arr[i] == 0) {
                continue;
            }
            for(int j = i+1; j<n+1;j++) {
                if(arr[j] != 0 && arr[j]%i == 0) {
                    arr[j] = 0;
                }
            }
        }
        
        for(int i = 1;i<n+1;i++) {
            if(arr[i] != 0) {
                result++;
            }
        }
        
        return result;
    }
 
    public static void main(String[] args) {
        NumOfPrime prime = new NumOfPrime();
        System.out.println(prime.numberOfPrime(10));
    }
 
}

1은 소수가 아니기 때문에 2부터 초기화를 해주었다.