3641-Pseudoprime numbers

問題（外部リンク）

3641 -- Pseudoprime numbers

実装の概要

となっているかを判断する問題ですが、注意点がいくつかあります。
まず、pの値が大きいので乗算を普通のループで計算すると間に合いません。そのためここでは繰り返し二乗法を使います。
また、この問題で問われているのがpがaに対する"pseudoprime"かということです。pが素数の場合はa>1である限り上記の式を満たしますが、それは普通のprimeなので除外しなければなりません。
そこで乗算の前にまずpが素数かどうかを判定する必要がありますが、入力されうる全てのpに対してテーブルを作ってしまうとメモリが足りません。
そのためテーブル作成は途中までで妥協して、ある程度より大きい値の判定には「割れる値がないか順番にひたすら探す」という方法に切り替える必要があります（ある値がnならまで確認すれば重要なので間に合います）

public class Main {

	public static void main(String[] args) throws IOException {
		PrimeNumberGenerator pg = new PrimeNumberGenerator();
        	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));


        while(true){
        	String[] tmpArray = br.readLine().split(" ");

        	int p = Integer.parseInt(tmpArray[0]);
        	int a = Integer.parseInt(tmpArray[1]);

        	if(p == 0 && a == 0){
        		break;
        	}

        	//片方が素数ならno
        	if(pg.isPrime(p)){
        		System.out.println("no");
        		continue;
        	}
        	long result = repeatablePow(a, p, p);
        	if(result == a){
        		System.out.println("yes");
        	}
        	else {
        		System.out.println("no");
        	}
        }

	}

	static long repeatablePow(int x, int n, int mod){
        if(n == 0){
            return 1;
        }
        long result = repeatablePow((int)((long)x*x%mod), n/2, mod);
        if(n % 2 == 1){
            result = result*x%mod;
        }
        return result;
    }

}

class PrimeNumberGenerator {
	int N = 10000001;
    private boolean[] isPrime= new boolean[N];

    public PrimeNumberGenerator() {
        Arrays.fill(isPrime, true);

        isPrime[0] = false;
        isPrime[1] = false;
        isPrime[2] = true;

        int limit = (int)Math.sqrt(isPrime.length);
        for(int i = 3; i <= limit; i+=2){
            if(isPrime[i] == false){
                continue;
            }

            for(int j = i * 2; j <= isPrime.length - 1; j += i){
                isPrime[j] = false;
            }
        }
    }

    public boolean isPrime(int index){
    	//ある程度以上大きいものについてはその都度ループを回して判定
    	if(index >= N){
    		int limit = (int)Math.sqrt(index);

    		if(index%2 == 0){
    			return false;
    		}
    		for(int i = 3; i <= limit ; i += 2){
    			if(index%i == 0){
    				return false;
    			}
    		}

    		return true;
    	}

    	else if(index % 2 == 0 && index != 2){
            return false;
        }
        return isPrime[index];
    }
}