[Java] BigInteger 클래스

• BigInteger는 Java에서 기본적으로 제공하는 정수 타입(int, long)보다 더 큰 정수를 다룰 수 있도록 설계된 클래스이다.
• int는 32비트 정수(약 ±21억), long은 64비트 정수(약 ±9경)까지만 저장할 수 있지만, BigInteger는 이보다 훨씬 큰 정수(무한대)를 다룰 수 있다.

---

생성

문자열을 이용한 생성

import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        BigInteger bigInt1 = new BigInteger("123456789012345678901234567890");
        System.out.println(bigInt1);  // 123456789012345678901234567890
    }
}

• 문자열을 이용하여 매우 큰 정수를 저장할 수 있다.

 

valueOf(long)을 이용한 생성

BigInteger bigInt2 = BigInteger.valueOf(1000000000L);
System.out.println(bigInt2);  // 1000000000

• 기본형 long 값을 BigInteger로 변환할 때 사용한다.
• 단, valueOf()는 long 범위를 초과하는 값을 생성할 수 없다.

 

사칙연산

• BigInteger는 기본 자료형처럼 +, -, *, / 연산자를 사용할 수 없고, 전용 메서드를 사용해야 한다.

BigInteger bigNumber1 = new BigInteger("100000");
BigInteger bigNumber2 = new BigInteger("10000");

System.out.println("덧셈(+) :" +bigNumber1.add(bigNumber2));
System.out.println("뺄셈(-) :" +bigNumber1.subtract(bigNumber2));
System.out.println("곱셈(*) :" +bigNumber1.multiply(bigNumber2));
System.out.println("나눗셈(/) :" +bigNumber1.divide(bigNumber2));
System.out.println("나머지(%) :" +bigNumber1.remainder(bigNumber2));

 

 

소수 판별

isProbablePrime(int certainty)

BigInteger 클래스의 isProbablePrime(int certainty) 메서드는 해당 숫자가 소수일 확률을 판별하는 기능을 제공한다.

BigInteger prime = new BigInteger("999999937");  // 큰 소수
System.out.println(prime.isProbablePrime(10));   // true (소수일 확률이 높음)

prime.isProbablePrime(10)

• isProbablePrime(int certainty) 메서드를 호출하여 숫자가 소수인지 판별한다.
• certainty 값이 10이므로, 이 숫자가 소수일 확률이 매우 높음을 의미한다.
• 결과가 true이면, "999999937"이 소수일 가능성이 매우 높다는 의미이다.

 

isProbablePrime(int certainty) 메서드 동작 방식

완벽한 소수 판별이 아니라 확률적인 소수 판별 알고리즘을 사용한다.

certainty 값이 클수록 소수일 확률이 증가한다.

내부적으로 밀러-라빈(Miller-Rabin) 소수 판별법을 사용한다.

certainty 값의 의미
certainty = 1 → 오차 확률이 1/2 (50%)
certainty = 5 → 오차 확률이 1/2⁵ = 1/32 (약 3%)
certainty = 10 → 오차 확률이 1/2¹⁰ = 1/1024 (약 0.1%)
certainty = 100 → 오차 확률이 1/2¹⁰⁰ ≈ 0% (거의 확실한 소수)즉, certainty = 10이면 소수가 아닐 확률은 약 0.1%이며, 거의 소수로 간주할 수 있다.

당연히 certainty 값이 클수록 속도는 느려진다.

 

완전한 소수 판별을 원하면 BigInteger.nextProbablePrime()을 사용할 수 있다.

 

BigInteger.nextProbablePrime()

BigInteger prime = new BigInteger("999999937");
BigInteger nextPrime = prime.nextProbablePrime();
System.out.println(nextPrime);  // 1000000007 (다음 소수)

nextProbablePrime()은 해당 숫자 이후의 가장 가까운 소수를 반환한다.