[Java] 스트림을 이용한 소수 구하기

요즘 이펙티브 자바 Third 에디션 책을 동네 도서관에서 대여해서 읽고있습니다.

스트림 병렬화에 대한 글을 읽다가 소수구하는 로직을 스트림으로 작성한 부분을 보게되었습니다.

소수구하기 로직은 이직준비 할 때나 다시 들여다볼만한거라 오래전에 for-loop 로 구현해본 기억만 있다보니 신선하게 느껴졌네요.

아직도 많은 블로그들에서 for-loop를 이용한 방법들만 많이 소개하고 있기도 하고해서 포스팅 주제로 삼아봤습니다. 

개인적인 기록도 할겸...

책을 읽고 새로 알게된 부분은 스트림에 대한 부분도 있지만 이미 BigInteger 클래스에 isProbablePrime 이란 메서드가 있었다는 겁니다..

 

아래는 특정 숫자 n 까지 소수가 몇 개인지를 출력하고, 그 목록도 출력하는 것을 테스트한 코드입니다.

public static void main(String[] args) {
    int n = (int) Math.pow(10, 8);
    // n 까지의 수 중에 소수의 개수 출력하기
    long cnt = LongStream.rangeClosed(2, n)
    	    .parallel()
            .mapToObj(BigInteger::valueOf)
            .filter(i -> i.isProbablePrime(50))
            .count();
    System.out.println(cnt);

    // n 까지의 수 중에 소수 목록 출력하기
    System.out.println(LongStream.rangeClosed(2, n)
            .mapToObj(BigInteger::valueOf)
            .filter(i -> i.isProbablePrime(50))
            .collect(Collectors.toList()));
}

LongStream을 이용하여 숫자의 범위를 정하고 mapToObj 를 이용하여 BigInteger로 변형한뒤 BigInteger.isProbablePrime(int certainty) 메서드를 필터로 전달하여 소수를 구하고 있습니다.

BigInteger.isProbablePrime(int certainty) 메서드는 소수를 구하기위해 내부적으로 밀러-라빈(Miller-Rabin) 테스트와 루카스-레머(Lucas-Lehmer) 테스트를 사용하고 있고요. 여기서 사용된 밀러라빈 테스트는 DSA(Digital Signiture Algorithm) 스펙 (NIST FIPS 186-2)을 기반으로 했다고 합니다. 이 스펙은 파일로 첨부하니 관심있으신 분들은 다운받아 보셔도 될 것 같네요. 

 

fips186-2.pdf

0.35MB

 

참고로 .parallel() 은 스트림에서 사용할 때 매우 주의를 요하는 기능입니다. 책에서는 이렇게 얘기합니다. Stream.iterate 를 데이터 소스로 이용하거나 중간 연산으로 limit 을 사용하는 스트림 파이프라인에서는 parallel을 이용한 성능개선을 기대할 수 없으며 오히려 안좋아질 수도 있다고 말이죠. 실제로 운영환경에서 저것 때문에 이슈가 발생한 적도 있었습니다. 그냥 무한루프에 빠진것처럼 쓰레드 하나가 먹통이 되어버리더군요. 스트림에서 병렬연산에 적합한 적은 reduce, min, max, count, sum 등의 연산이며, collect처럼 가변축소를 수행하는 메서드는 병렬연산에 적합하지 않다고 합니다. 참고하시기 바랍니다.