Primes

isPrime

public boolean isPrime(int n) {
  for (int d = 2; d <= Math.sqrt(n); d++) {
    if (n % d == 0) return false;
  }
  return n > 1;
}

public boolean isPrime(int n) {
  for (int d = (int)Math.sqrt(n); d >= 2; d--) {
    if (n % d == 0) return false;
  }
  return n > 1;
}

Do you think one of these will be faster, on average, than the other?

Results of microbenchmark

Testing all numbers from 1 to 1,000,000:

• Looping up: 5780 numbers/millisecond

• Looping down: 1133 numbers/millisecond

I.e. Up is over five times as fast as down.

Primes below

public int numberOfPrimesBelow(int bound) {
  int count = 0;
  for (int n = 2; n < bound; n++) {
    if (isPrime(n)) {
      count++;
    }
  }
  return count;
}

This is simple counting loop.

Twin primes below

public int numberOfTwinPrimePairsBelow(int bound) {
  int count = 0;
  for (int n = 0; n < bound; n++) {
    if (isPrime(n) && isPrime(n + 2)) {
      count++;
    }
  }
  return count;
}

This is also a simple counting loop.

Only difference is the thing we’re counting is a bit more complex.

isSuperPrime

public boolean isSuperPrime(int n) {
  return isPrime(n) && isPrime(numberOfPrimesBelow(n) + 1);
}

Note that the order of expressions in the && doesn’t matter for correctness but does affect performance.

Do the cheap thing first and you might not have to do the expensive thing.