Pseudoprime Numbers (POJ 3641)

A number is pseudoprime numbers if and only if power(a, p) % p == a and p is prime. So we apply quick power calculation with mod and using dividing to method to test if is prime.

import java.io.*;
import java.util.*;

public class PseudoPrimeNumbers {
    private static long power(long a, long b) {
        long r = 1;
        long mod = b;
        while (b > 0) {
            if ((b & 1) == 1) r = (r * a) % mod;
            a = (a * a) % mod;
            b >>= 1;
        }
        return r;
    }
    private static boolean isPrime(long N) {
        for(long i = 2; i * i <= N; i++) {
            if ((N % i) == 0) return false;
        }
        return true;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()) {
            long p = in.nextLong(), a = in.nextLong();
            if (a == 0 && p == 0) return;

            System.out.println((power(a, p) == a && !isPrime(p)) ? "yes" : "no");
        }
    }
}