Это самый элегантный способ:
public static boolean isPrime(int n) { return !new String(new char[n]).matches(".?|(..+?)\\1+"); }
Java 1.4+. Импорт не требуется.
Так коротка. Так красиво.