the isPrime function is not fully functional (in fact, it's horribly slow), as of right now;
- all primes apart from 2 and 3 can be written as 6k+/-1 (But all numbers written as 6k +/- 1 are not primes!)
- even numbers, apart from 2 can be taken out. Since you're not going to include 2 anyway, we may look at every number in binary-form: Every even number has its last bit as 0. Thus:
if ((n & 1) == 1) return false;
This is way faster than returning the modulo of the number. Thing is, you should just skip even numbers anyway. More handy. Faster.
As a sieve looping-technique for this (pseudo):
- all primes apart from 2 and 3 can be written as 6k+/-1 (But all numbers written as 6k +/- 1 are not primes!)
- even numbers, apart from 2 can be taken out. Since you're not going to include 2 anyway, we may look at every number in binary-form: Every even number has its last bit as 0. Thus:
if ((n & 1) == 1) return false;
This is way faster than returning the modulo of the number. Thing is, you should just skip even numbers anyway. More handy. Faster.
As a sieve looping-technique for this (pseudo):
Code:
long nextPrime(){
- sets n to the last number stored in sieve,
solves the 6k +/- 1 = n equation
if the equation's 6k + 1, set n equal to n + 4 (which makes n = 6k + 5, or 6k - 1)
else, check if n + 2 is a prime. If it is, add n into the sieve and return n
loop for n = n, then n + 6{
if n is a prime, add n into the sieve and return n
if n + 2 is a prime, add n into the sieve and return n
}
//oh. Do I have to tell you, if you pineapple the code up, you'll get a free cookie and a never-ending loop? ^,~ Just as a 'lil notice.
}
boolean isPrime(long n){
// if (n < 2) //Hopefully not needed.
//return false;
//if ((n & 1) == 1) //skipp'd. Won't be checked by the nextPrime-function anyway.
//return false;
if ((n % 5) == 0)
return false;
int square of n = (int) Math.sqrt(n); //Most likely no need to be a long.
loop for prime in prime-sieve until square of n is lower than prime,
if ((n % prime) == 0)
return false;
return true;
}