Java prime number calculator

[bevolasko]

Just for curiosity, I wanted to see how fast my computer can calculate prime numbers. I'm planning to write the program in java and use threads to speed up the process. The only problem I'm facing is the fact that it'll be working with very large numbers, much larger than 2^64. I've heard of the BigInteger class but I'm very unfamiliar with it. I don't know how to implement it in the code and use simple algebraic calculations with it. If you have some suggestions on how to use BigInteger I would be very pleased if you could help.

Anyways, the program will work by calculating a number using the Mersenne form 2^x - 1 inside an infinite loop. Then at every cycle the number will be then verified if it is prime or not. The prime number will be printed on the console. That's it.

I'm probably gonna write two programs which do the same thing one with threading and the other without just to see the differences.

 

[carnageX]

Java: How to use BigInteger? - Stack Overflow

 

[tommyboy123x]

I've been thinking of making a class to handle this kind of problem... basically making an object that is an array of numbers valued between 0 and 9 to represent each decimal place.

So when it comes time to add 52142 + (super-large number), you loop through doing something like

int num = 52142;
//huge number = 9999999999999999999999999
for (int x = 0; num > 0; x++) {
   int s = num % 10;
   num = num / 10;
   decimals[x] += s;
   //recurse here if decimals[x] is over 9
   }

Multiplication (and division) could be done using the process you do when you would multiply 52*8 on paper by hand.


Reason I haven't done it yet is I think it could be a lot more efficient... ehhem... BigInteger (Java Platform SE 6)

 

[bevolasko]

That could slow things a bit

Anyways, I ran the program and in under 6 & 1/2 minutes the program calculated all the first 20 Mersenne primes which are from 2^2-1 to 2^4423-1. A few hours have past and the computer has yet to calculate the next MP 2^9689-1 which is exponentially large. I would estimate that it could take days for it calculate but I may be wrong.

Given the time it took to find M20 (2^4423-1) I believe it's possible to princely figure out how much time it would take to calculate M21 (2^9689-1). Any good mathematicians here?

EDIT: Never mind the computer calculated M21 in 9 hours, 55 minutes and 26 seconds of execution time without any threaded optimization. Next one is 2^9941-1.