[Java] Stream을 이용해 Lazy하게 소수 구하기

흔히 n이 소수인지를 확인하기 위해서는 2부터 n - 1까지 n을 나눠가면서 나누어 떨어지는지 여부를 검사한다.

이 방법에서 최적화 몇 가지를 적용하여 더욱 효율적으로 개선하고, Stream을 이용하여 lazy evaluation을 적용해보자.

Naive한 방법

다음은 n이 소수인지를 검사하는 naive한 방법이다.

개선 사항

• n = a x b 로 표현할 때, a > b라고 가정해도 일반성을 잃지 않는다.
  즉, i는 sqrt(n)까지만 검사해도 된다. sqrt() 연산은 비싸므로, i * i <= n 조건으로 대체할 수 있다.
• 5 이상의 소수는 6k ± 1의 형태를 띈다. 따라서 i는 6씩 증가하면서, 검사해주면 검사 횟수를 줄일 수 있다.

개선된 방법

Stream으로 Lazy Evaluation 적용하기

Java의 Stream은 List와 다르게 연산이 정의되었을 때 바로 연산을 수행하지 않는다.

각 원소들을 어떻게 계산하는지 정의된 상태로 대기하다가, 특정 원소가 필요할 때 그 원소를 구하기 위한 연산만 수행한다.

이를 이용하면 다음과 같이 소수를 구하는 Stream을 만들 수 있다.

실행 결과

전체 코드

실행 결과