Count Primes up to N (Sieve of Eratosthenes)

/*
 * Problem : Count the primes up to n.
 * Input   : One integer n.
 * Output  : The count of primes <= n.
 * Approach: Cross out multiples with a sieve.
 * Time    : O(n log log n)
 * Space   : O(n)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static long solve(long n) {
        // Step 1: Make a table. Every number from 0 to n is "maybe prime" at the start.
        if (n < 2) {
            return 0;
        }
        boolean[] isPrime = new boolean[(int) n + 1];
        java.util.Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;

        // Step 2: For each prime p, cross out its multiples, starting at p * p.
        for (int p = 2; (long) p * p <= n; p++) {
            if (isPrime[p]) {
                for (int multiple = p * p; multiple <= n; multiple += p) {
                    isPrime[multiple] = false;
                }
            }
        }

        // Step 3: Count the numbers that are still marked prime.
        long count = 0;
        for (int i = 2; i <= n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        System.out.println(solve(n));
    }
}