Prime Number

Examples

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;
}

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;
}

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;
}