project euler problem 418

Factorisation triples

This is an easy problem. When the problem is posted, I felt that it is not very difficult. It looks like similar to problem 266, but I did not play with it seriously. Today, I still do not have too much clue on it.  I tried to answer some fundamental questions like "how to express 43! in terms of prime numbers and how many factors does 43! have". After a while, I see what I need to do. I implemented some simple code and it takes 500 seconds to get the answer! It is slow, however the answer is correct. I optimized my code and tried to start searching in a different place. It only takes 5 seconds to get the answer.

project euler problem 245

Coresilience

 A very difficult problem. 

 I lost my old code. I only left a several-lines comment in my computer. It says my old code runs for 80 seconds to get the answer. 

This time, I want to see if I can make it faster by myself. I found that I cannot solve it!  I believe it can be solved only by brute force. After some time's thought, and with the help of my comment. The problem is solved in one minute. My method is almost all brute force, but I found some property from the equation that can reduce the search space.

I read the discussion, I found there is a much better way to solve the problem. I implemented the new method. The problem is solved in 5 seconds.

 

project euler problem 251

Cardano Triplets

This problem is very difficult. I checked my old code, it runs very slow because I was using a very inefficient factor method. So I changed to a sieve method for factorization, which is much faster. My original code runs for 3 and a half minutes. After this optimization, my code runs for 7 seconds.

After I checked the discussion, I found a very efficient algorithm by linguo in the second page. It only takes 1.6 second. The extended euclidean algorithm in his code is very fast.

project euler problem 224

Almost right-angled triangles II, revisit

This problem is related to problem 221 and 223. If you solve either of them, this one is not that hard. Otherwise, the solution might be very costly.  I tried factorization method. Although I have used some of the result from previous problem, it is still very slow. It takes 20 seconds. I will try Doraki's algorithm tomorrow. 

project euler problem 223

Almost right-angled triangles I, Revisit

This problem is very difficult.  One algorithm is easy to come up with. But it is not very efficient. It is quite slow. My code runs for 20 seconds. Doraki provided a very nice algorithm in the first page.  It only takes a few seconds using Doraki's algorithm. I am very eager to know if there is any efficient method to solve it in one second.

project euler problem 159

Digital root sums of factorisations

An excellent problem. I like it. Although it is easy to get the correct answer, but it is not that simple to solve it in 50 ms.

I checked my old code. I used pure brute force. It takes 3 seconds. I did some optimization and reduced to 0.5 second. 

Then I read the discussion thread. I found the post from Robert_Gerbicz, a legendary figure in Project Euler forum. I tried his method. Oh, my god, he made it in 40ms. I read his post, it is really amazing!

project euler problem 047

Distinct primes factors

I revisited this problem tonight, I found it was the first problem involving factors. In many PE problems, factor plays a significant role. 

I am pretty sure that when I started working on PE problems, I had no idea that sieve method can help to find factor or number of distinct factors. I thought that sieve method was only used to create prime table. 

I learned sieve method for factor when I tried to solve a problem numbered around 200 simply because my method was too slow. 

Please review the discussion thread if your method is not elegant. 

project euler problem 003

largest prime factor

I use C or C++ to solve project euler problems. But I rarely use long long in coding. After I solved 50 to 100 problems, I found long long is necessity. The problem is easy, even one use some kind of  brute force method. One may read the book from CLRS and try some fancy method. 

It is interesting to notice that for most of the project euler problems that require an integer as an answer, number is usually less than 2^64.