# HackerRank Solutions – Time Complexity – Primality – Java Solution

All credits to Rodney Shaghoulian for this simple solution for the HackerRank challenge – Time Complexity – Primality. This solution is written in Java.

// Author: Rodney Shaghoulian // Github: github.com/RodneyShag import java.util.Scanner; // Time Complexity: O(n^(1/2)) for each // Space Complexity: O(1) public class Solution { public static void main(String[] args) { Scanner scan = new Scanner(System.in); int p = scan.nextInt(); while (p-- > 0) { int n = scan.nextInt(); System.out.println(isPrime(n) ? "Prime" : "Not prime"); } scan.close(); } public static boolean isPrime(int n) { if (n < 2) { return false; } else if (n == 2) { // account for even numbers now, so that we can do i+=2 in loop below return true; } else if (n % 2 == 0) { // account for even numbers now, so that we can do i+=2 in loop below return false; } int sqrt = (int) Math.sqrt(n); for (int i = 3; i <= sqrt; i += 2) { // skips even numbers for faster results if (n % i == 0) { return false; } } return true; } }