For my first game, Mr Tiddles, I decided to add achievements via Google Game Services. One of these achievements is "Finish game with a prime score".
Prime numbers are natural numbers greater than 1 that are only divisible by 1 and itself. The easiest most straight-forward way to check if n is prime:
private boolean isPrime(int n) {
if (n == 0 || n == 1) return false;
double limit = Math.sqrt(n);
for (int i=2; i <= limit; i++) {
if (n % i == 0) return false;
}
return true;
}This will definitely work, but if n is a large prime, it would have to iterate through a lot of numbers before coming to a conclusion. Good news is, there is a better and more efficeint way!
A quick Google search reveals a Wikipedia page on Primality tests. There are many methods/approches listed there, I gravitated towards one particular description under Naive methods.
All primes (except 2 and 3) can be expressed as 6k±1 for some integer k
This blew my mind away. I had never thought of prime numbers this way. Despite the explanation making sense, I still had to double check with a handful of prime numbers - of course the statement held true :)
Although this approach is not the most efficient, I chose it because I could actually understand it and felt it would be easy enough to implement. So, a more efficient way of determining a prime is as follows:
private boolean isPrime(int n) {
if (n == 0 || n == 1) return false;
if (n % 2 == 0 || n % 3 == 0) return false;
double limit = Math.sqrt(n);
for (int k = 1; 6*k-1 <= limit; k++) {
if (n % (6*k-1) == 0 || n % (6*k+1) == 0) return false;
}
return true;
}