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…

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: