============
Prime Number
============

--------
Examples
--------

Java
====

.. code-block:: java

  boolean primeNaive(int n) {
    if (n < 2) {
      return false;
    }
    for (int i = 2; i < n; i++) {
      if (n % i == 0) {
        return false;
      }
    }
    return true;
  }

.. code-block:: java

  boolean primeSlightlyBetter(int n) {
    if (n < 2) {
      return false;
    }
    int sqrt = (int) Math.sqrt(n);
    for (int i = 2; i <= sqrt; i++) {
      if (n % i == 0) return false;
    }
    return true;
  }

.. code-block:: java

  boolean[] sieveOfEratosthenes(int max) {
    boolean[] flags = new boolean[max + 1];
    int count = 0;

    init(flags);
    int prime = 2;

    while (prime <= max) {
      crossOff(flags, prime);

      prime = getNextPrime(flags, prime);

      if (prime >= flags.length) {
        break;
      }
    }

    return flags;
  }

  void crossOff(boolean[] flags, int prime) {
    for (int i = prime * prime; i < flags.length; i += prime) {
      flags[i] = false;
    }
  }

  int getNextPrime(boolean[] flags, int prime) {
    int next = prime + 1;
    while (next < flags.length && !flags[next]) {
      next++;
    }
    return next;
  }