# Prime numbers utilites

I have been solving problem 58 and have found a really stupid mistake in dynamic search in my Prime class. Code updated.

In the method isDivisble(long) the condition was “i < Prime.size()” while it should be “PRIME.get(i) * PRIME.get(i) <= number”. Why? Let me describe it on the example. Suppose that we have generated all prime numbers below one hundred million and now we are checking if 100000007 is prime (it’s first prime number above 10^8). If the number was divisible by a number greater than its square root, it would be also divisible by something smaller than its square root. So it is sufficient to check only those divisors which are below the square root of a number. With the first condition dividing was continued until all found prime numbers have been checked, which in this case is quite a lot. This change has greatly improved dynamic search.

And how about problem 58? Well, I have written an algorithm which DOES NOT generate an array and it has crashed (heap space) after about 20 minutes (I think it should find an answer within 30-40 minutes). I am really interested about others’ solutions. For know I have a feeling that a boolean in Java (in array) is at least 8 bits large… Array of booleans of length 10^9 should fit in 125MB of memory, but with 1GB memory given, JVM is able to create an array only for half of it :/ I will try to figure it out when I will be less tired…

Posted on June 29, 2011, in Project Euler. Bookmark the permalink. Leave a comment.

## Leave a comment

## Comments 0