Day 25: HackerRank 30 Days Of Code Solution | Running Time and Complexity

Day 25 of HackerRank's 30 Days of Code is about running time, and it uses the oldest example in the book: checking whether a number is prime. The point is not the prime test itself. It is learning to look at a loop and ask how many times it will run for the biggest input, and then cutting that number down with a bit of maths.

Here the inputs go up to 2 x 10^9. A loop that tries every divisor up to n would need two billion steps for a single prime, which is far too slow. Stopping at the square root brings that down to about 45,000. That jump from O(n) to O(√n) is the lesson of the day.

Problem

A prime is a natural number greater than 1 whose only positive divisors are 1 and itself. For each given number n, print Prime if it is prime and Not prime otherwise. HackerRank suggests aiming for an O(√n) solution.

Input format: the first line has T, the number of test cases. Each of the next T lines has one integer n.

Output format: for each test case, print Prime or Not prime on its own line. Note the exact spelling: capital P, lowercase "prime" in "Not prime".

Constraints: 1 <= T <= 30, 1 <= n <= 2 x 10^9.

Input
3
12
5
7

Output
Not prime
Prime
Prime

Approach

Start with the key fact. If n has a divisor d bigger than √n, then n / d is also a divisor, and it is smaller than √n. Divisors come in pairs, one on each side of the square root. So if nothing up to √n divides n, nothing above it can either.

1. Numbers below 2 are not prime. This covers n = 1, which is allowed by the constraints and is a common source of wrong answers.
2. 2 and 3 are prime.
3. Any other even number is not prime.
4. For odd n, try odd divisors i = 3, 5, 7, ... while i * i <= n. If any divides n, it is not prime.
5. If the loop finishes, n is prime.

Skipping even divisors halves the work again. For the largest input that is about 22,000 checks, and with at most 30 test cases the whole run is well under a second.

Dry run: n = 12 is even and not 2, so Not prime. n = 5: odd, start at i = 3, 3 x 3 = 9 is more than 5, the loop never runs, Prime. n = 7: 9 is more than 7, Prime.

Solution in Java

The older solution here was correct. It used i <= Math.sqrt(n) and checked every number, odd or even. The version below uses i * i <= n with long, which avoids floating point entirely, and skips even divisors.

import java.util.Scanner;

public class Solution {

    // Trial division up to the square root of n: O(sqrt(n)).
    static boolean isPrime(long n) {
        if (n < 2) return false;          // 1 is not prime
        if (n < 4) return true;           // 2 and 3
        if (n % 2 == 0) return false;     // even numbers other than 2
        // Only odd divisors are left to try.
        // i * i <= n avoids Math.sqrt, and long keeps i * i from overflowing.
        for (long i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        StringBuilder out = new StringBuilder();
        while (t-- > 0) {
            long n = sc.nextLong();
            out.append(isPrime(n) ? "Prime" : "Not prime").append('\n');
        }
        System.out.print(out);
    }
}

Why long? If i were an int, then near the top of the range i * i could overflow. For example, 46341 * 46341 as an int prints -2147479015, a negative number, which would make the loop condition behave wrongly. As a long it is 2147488281, as expected.

Edge cases I tested: 1 gives Not prime, 2 gives Prime, 9 gives Not prime (a perfect square, caught exactly when i = 3), 2000000000 gives Not prime, 1999999973 gives Prime (I confirmed this with a separate Python check), and 2147483647 gives Prime. Thirty copies of 1999999973 ran in about 0.13 seconds, including JVM start-up.

Output

Not prime
Prime
Prime

Complexity

Time: O(√n) per test case, so O(T √n) overall. The naive loop up to n is O(n), which for 2 x 10^9 is around 45,000 times slower in the worst case.

Space: O(1).

Common mistakes

• Calling 1 prime. With a loop starting at 2, n = 1 never finds a divisor, so the code wrongly prints Prime unless you handle it first.
• Stopping before the square root. Using i < Math.sqrt(n) instead of <= misses perfect squares like 9 and 25.
• int overflow in i * i. Use long, or compare i <= n / i.
• Wrong output text. "Not Prime" with a capital P fails on HackerRank. Copy the expected strings exactly.

Related: Java Primality Test handles numbers with up to 100 digits using BigInteger, and Analysis of Algorithms explains Big-O in more depth.

Tip: try to solve the problem yourself before reading the solution. Use the code as a reference to check your approach, and make sure you understand why it works.

More HackerRank solutions All coding problems MCQ practice