Java 判斷質數

判斷質數

輸入: 2 < n < 2147483647

import java.util.Scanner;
import java.math.BigInteger;

public class Prime {
  
    public static boolean MillerRabin(BigInteger x, int d, int time, BigInteger n){
        BigInteger nDivOne = n.subtract( BigInteger.ONE );
        BigInteger TWO = BigInteger.valueOf(2);
        x = x.modPow(BigInteger.valueOf(d), n);
  
        // x = a ^ d mod n，若x=1 or x=n-1，直接跳過
        if( !x.equals( BigInteger.ONE ) && !x.equals( nDivOne ) ){
   
            //在S-1的次數內，x = x ^ 2 mod n，若x=n-1 直接跳過
            while( --time > 0 ){
                x = x.modPow(TWO, n);
                if( x.equals( nDivOne ) ){ return true; }
            }
            return false;
        }
        return true;
 }
 
    public static boolean isPrime(int n){  
        // (x ^ s) * d = n - 1
        int d = n - 1;
        int s = 0;
        while( d % 2 == 0 ){
            d /= 2;
            s++;
        }
  
        return MillerRabin(BigInteger.valueOf(2), d, s, BigInteger.valueOf(n)) &&
               MillerRabin(BigInteger.valueOf(7), d, s, BigInteger.valueOf(n)) &&
               MillerRabin(BigInteger.valueOf(61), d, s, BigInteger.valueOf(n));
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int num;
  
        while( sc.hasNext() ){
            try{
                num = sc.nextInt();
            }catch(java.util.InputMismatchException e){
                break;
            }
    
            switch( num ){
                case 2: case 5: case 7: case 61:
                    System.out.println( "質數" );
                    break;
                default:
                    switch( num % 10 ){
                        case 1: case 3: case 7: case 9:
                            System.out.println( isPrime(num) ? "質數" : "非質數" );
                            break;
                        default:
                            System.out.println( "非質數" );
                        break;
                    }
                    break;
            }
        }
     }
}

寫完之後，發現記憶體用量異常的大，不知道是不是因為使用BigInteger物件的關係，哈