[Java] 소수판별법 : 에라토스테네스의 체

소수 판별시 모든 수를 순환하면서 루프로 나누어 떨어지는지를 확인하는것은 매우 비효율적이며 시간초과가 날 수 있다.

이를 빠르게 해결해주는 알고리즘

에라토스테네스의 체

간단하게 루프를 돌며 해당수의 배수를 모두 제거해버리는 방식으로 진행된다.

아래 코드는 매개변수 n 을 받았을 때 n 보다 작은 모든 소수를 배열로 반환하는 코드이다.

public static int[] solution(int n) {

	// 배열 크기를 가늠할 수 없으므로 리스트에 추가할 예정
	List<Integer> list = new ArrayList<>();
		
        // 입력받은 값보다 1 만큼 큰 배열을 생성해준다.
        int[] arr = new int[n + 1];

		// 0과 1은 소수가 아니므로 2부터 입력받은 n 까지 값으로 초기화해준다.
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }

		// 2부터 n 까지 루프를 돌면서 소수를 판별한다.
        for (int i = 2; i <= n; i++) {
        	
            // 만약 해당 배열의 값이 0이라면 무시한다.
            if (arr[i] == 0) {
                continue;
            }

			// 현재 i 인덱스의 2배수의 값을 모두 소거한다.
            // 2, 4, 6, 8, 10
            // 3, 6, 9, 12, 15
            for (int j = i * 2; j <= n; j += i) {
                arr[j] = 0;
            }
        }

		// 마지막으로 배열의 값이 0이 아니라면 리스트에 추가한다.
        for (int i : arr) {
            if (i != 0) {
                list.add(i);
            }
        }

		// stream을 사용하여 리스트를 배열로 변환하여 리턴한다.
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

이러한 알고리즘을 이용하니 시간초과가 나는 문제들이 해결됐다.