51nod 1186 대수 소수 판단 (java) +. isProbablePrime (int certainty) 알 아 보기

정수 N 을 1 개 주 고 N 이 양수 인지 확인 합 니 다."Yes" 를 출력 하지 않 으 면 "No" 를 출력 합 니 다.
Input

     N(2 <= N <= 10^30)

Output

  N   ，  "Yes"，    "No"。

입력 예제

17

출력 예제

Yes

    

import java.math.BigInteger;
import java.util.Scanner;
public class Bigshu {
	public static void main(String[] args)
	{
		Scanner cin = new Scanner(System.in);
		BigInteger x;
		x = cin.nextBigInteger();
		if(x.isProbablePrime(1))
			System.out.println("Yes");
		else
			System.out.println("No");
	}
}

. isProbable Prime (int certainty): 이 BigInteger 가 소수 일 수 있다 면 true 로 돌아 갑 니 다.만약 그것 이 하나의 합 수 라 는 것 이 명확 하 다 면, false 로 돌아 갑 니 다.매개 변수 certainty 는 호출 자가 참 고 싶 어 하 는 불확실 성 측정 입 니 다. 이 수가 소수 일 확률 이 1 - 1 / 2 * certainty 방법 을 초과 하면 이 방법 은 true 로 돌아 갑 니 다.실행 시간 은 매개 변수의 확정 값 에 정비례 한다.
자바 의 isProbable Prime 함 수 는 BigInteger 류 에 대한 소수 판단 함수 입 니 다. 그 실현 원 리 는 복잡 하지 않 습 니 다. 단지 여러 상황 으로 나 누 어 토론 해 야 합 니 다. Miller - Rabin 소수 테스트 와 Lucas - Lehmer 테스트 를 사용 해 야 합 니 다. 이것 은 확률 알고리즘 입 니 다. 돌아 온 결과: 한 수 는 소수 가 아니 거나 한 수 는 소수 일 수 있 습 니 다.다음은 jdk 1.6 src 의 주요 소스 코드 입 니 다.

public boolean isProbablePrime(int certainty) {
        if (certainty <= 0)
            return true;
        BigInteger w = this.abs();
        if (w.equals(TWO))
            return true;
        if (!w.testBit(0) || w.equals(ONE))
            return false;

        return w.primeToCertainty(certainty, null);
    }

  public boolean testBit(int n) {
        if (n < 0)
            throw new ArithmeticException("Negative bit address");

        return (getInt(n >>> 5) & (1 << (n & 31))) != 0;
    }

   private int getInt(int n) {
        if (n < 0)
            return 0;
        if (n >= mag.length)
            return signInt();

        int magInt = mag[mag.length-n-1];

        return (signum >= 0 ? magInt :
                (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
    }

  boolean primeToCertainty(int certainty, Random random) {
        int rounds = 0;
        int n = (Math.min(certainty, Integer.MAX_VALUE-1)+1)/2;

        // The relationship between the certainty and the number of rounds
        // we perform is given in the draft standard ANSI X9.80, "PRIME
        // NUMBER GENERATION, PRIMALITY TESTING, AND PRIMALITY CERTIFICATES".
        int sizeInBits = this.bitLength();
        if (sizeInBits < 100) {
            rounds = 50;
            rounds = n < rounds ? n : rounds;
            return passesMillerRabin(rounds, random);
        }

        if (sizeInBits < 256) {
            rounds = 27;
        } else if (sizeInBits < 512) {
            rounds = 15;
        } else if (sizeInBits < 768) {
            rounds = 8;
        } else if (sizeInBits < 1024) {
            rounds = 4;
        } else {
            rounds = 2;
        }
        rounds = n < rounds ? n : rounds;

        return passesMillerRabin(rounds, random) && passesLucasLehmer();
    }