22.4.29 [HackerRank]Java Primality Test

✅ 문제 분석

1보다 크면서 1과 자기 자신으로밖에 나누어 떨어지지 않는 소수에 관한 문제.

large integer인 n이 주어지면, 자바의 Biginteger 클래스인
isProbablePrime 메소드를 사용해 prime인지 not prime인지
출력해주면 된다.

🌱 배경지식

isProbablePrime 메소드

public boolean isProbablePrime(int certainty)

Biginteger 클래스 안의 메서드로, Miller-Rabis's algorithm에 바탕을 둔 확률적 소수 판별 함수이다.

이 메서드에 있는 certainty라는 인자가 중요한데, true를 반환하면 소수인지 확인하고자 하는 정수가 소수일 확률이 1-(1/2)^certainty의 확률을 넘는다는 의미이다.
보통 certainty가 10인 경우 소수일 확률이 0.9990234375정도이므로 웬만한 큰 수의 소수는 판별할 수 있다.

✏️ 해설

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;



public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String n = bufferedReader.readLine();
		//줄 단위로 text를 읽어즐이고, stream의 끝에 다다르면 (EOF) null값을 반환한다. 
        bufferedReader.close();
        // BigInteger 클래스를 이용해 정수 n을 인자(argument)로 하는 새 객체 b를 하나 생성해준다.
        BigInteger b = new BigInteger(n); 
        //조건문을 돌려서 certainty가 10이면(=소수이면) prime 프린트, 아니면 not prime
        if (b.isProbablePrime(10)) {
            System.out.println("prime");
        } else {
            System.out.println("not prime");
        }
    }
}

👉 참고

• https://docs.oracle.com/javase/7/docs/api/java/math/BigInteger.html#isProbablePrime%28int%29