There are a number of minor improvements you could make - probably none of which will make any difference to the run time:
- Using
p % 2
may result in a division -p & 1
will not and therefore should be a fraction faster. - You could easily pre-calculate all primes up to a reasonable limit.
Math.pow(2,x)
is equaivalent to2 << x
in all cases and may well be much quicker.- Printing inside your loop is wasteful - you should collect all results in a list and print them at the end.
Apart from those trivial and probably premature optimisations - you should run the calculation a few hundred times and take the average time before attempting any optimisations.
BTW - Just because you are using nanotime
does not mean you are getting nanosecond resolution - far from it.
Also -
As the Wikipedia article points out - you could avoid much of your calculation by enumerating the common binary pattern mentioned there:
for ( int i = 0; i < 10; i++ ) {
long q = ((1 << (i+2)) - 1) << (i+1);
// Printing BigIntegers in binary is easy.
BigInteger bq = BigInteger.valueOf(q);
System.out.println(q+" = "+bq.toString(2));
}
6 = 110
28 = 11100
120 = 1111000
496 = 111110000
2016 = 11111100000
8128 = 1111111000000
32640 = 111111110000000
130816 = 11111111100000000
523776 = 1111111111000000000
2096128 = 111111111110000000000
Obviously you still have to test them but you don't have to test nearly as many.
Also - if you want to take it one step further into BigInteger
you could start with something like:
for ( int i = 0; i < 10; i++ ) {
BigInteger p = BigInteger.ONE.shiftLeft(i+2).subtract(BigInteger.ONE).shiftLeft(i+1);
System.out.println(p.toString(10)+" = "+p.toString(2));
//long q = ((1 << (i+2)) - 1) << (i+1);
//BigInteger bq = BigInteger.valueOf(q);
//System.out.println(" "+bq.toString(10)+" = "+bq.toString(2));
}