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 prolem 214

Totient Chains

This problem is not very interesting. It is pretty straight forward. I did not find a super fast solution in the discussion.  My code's runtime is 2.2 second. 

project euler problem 196

Prime triplets

This problem is relatively simple. One just needs to find all primes in range [low, high]. The problem is well defined and easy to solve. My code is not so nice. But it runs under 1 second. 

project euler problem 187

Semiprimes

This is a  really simple problem. It just shows the power of sieves one more time. No wonder more than 5500 people solved it.

project euler problem 124

Ordered radicals

This is a simple problem.  One can compare the numbers of solves on 124 and 122. Almost doubled! Sieve shows its power in this problem again! 

project euler problem 095

Amicable chains

I checked my old code. It was cumbersome. I used set and my algorithm to find all divisors was too slow. It takes 6.5 second to find the answer. 

This time, I changed the divisor sum algorithm by using some sieve method. But it is still not very fast since I used hashset to check if the number appeared in the sequence. It is kind of overkill. But this reduced the run time to 0.764 second. 

I read the discussion thread and find a better algorithm to stop the sequence. I reimplemented the code, it reduced to 0.196 second with my debug version. Sweet!

project euler problem 072

Counting fractions

I checked my old code. I was trying to factor each number n, then find the number of relative prime numbers to n. This time I directly calculate the totient function for each number, using sieve. 

It takes 3.6s to finish for the old code, while 0.076s for the new code.

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 035

circular primes

This is a simple problem,  it takes 0.014 second to find the answer. Not too bad. 

My first version was lost. I did not remember how I solved it.   I am happy that I did not split the number into digits in my second version. I see the same strategy on page 2 in the discussion thread.

project euler problem 023

non abundant sums

check my comments on  problem 021, same method. Once the algorithm is understood, this problem is simple. 

Probably the most difficult one so far.

project euler problem 021

amicable numbers

There is a neat solution in the discussion thread.  It got 5 kudos, which worth a careful read(in page 1)! This problem is very similar to problem 12.

project euler problem 012

This is not a difficult problem. You may try a much more difficult one, problem 378.  After I solved 378, I feel my divisor function is too complicated. 

I rewrote the code, now it  has only 30 lines. It took 0.004 second (my debug version).

project euler problem 010, very interesting problem

If you can solve problem 7, there is no difficulty to solve this one.  This can be a very simple problem using the sieve method.

But if you are really interested to count the primes or count the sum of primes under N, the sieve method is not efficient at all when N is large. In the discussion of this problem, a dynamic programming approach is suggested and it is a fast method to count prime numbers. Please do not miss the opportunity to learn if you do not know this method! The code is written in python,  and lucy did an excellent job in his post!

project euler problem 007

This is a warm-up problem.  Very basic.  Read the discussion thread if your code took more than 0.2 second.