Project Euler 124

Ordered radicals



This is an easy problem with only 25% difficulty rating and it costs me about 10min to code. My code runs in 0s.
The idea is so simple that we can calculate rad(n) for every n from 1 to 100000. As an optimization, a priority queue is used to keep the first 10000 smallest values.

Project Euler 306

Paper-strip Game


After reading problem description, It is evident that we need generate Grundy numbers from 1 to 10^6. But it will take a long period to do this. So what should we do in this case is to find if there is a pattern in Grundy numbers sequence. Brute-force to get the first several Grundy numbers and find that if we ignore non-zero values then it is a pattern.

Project Euler 521

Smallest prime factor




It’s really a hard problem for me but it forces me to learn a new algorithm that computing sum of all primes below n. My code runs in 550 seconds after using OpenMP as an optimization.
In order to solve this one, you’d better take a look at the method of counting primes that introduces a dp method to count the number of primes not exceeding n. This algo’s running time complexity is $O(n^{0.75})$ which is fast enough for this problem.
The most important thing this problem brings to me is that there are methods to compute sum of primes without generating all primes first.

Project Euler 491

Double pandigital number divisible by 11



This problem can be solve using dynamic programming. My code runs in nearly 0.0 seconds.
It is also works to enumerate all distinct permutations generated by given digits. Tha total amount of permutations should be 20!/(2^10) but I didn’t calculate what exactly the factorial is. I think it’s not difficult to figure out the dp solution.

Project Euler 357

Prime generating integers



Such problems are very straight forward, but if you want to make your code runs fast it needs several optimizations. My code runs in 4.04655s and I am not going to optimize it anymore.
There are several observations here:
1. n + 1 must be a prime.
2. n must be an even number cuz (n + 1) wouldn’t be a prime if n is an odd.
3. n is a squarefree number.

P.S. This is the 50th problem I have solved.

Project Euler 493

Under The Rainbow



It spent me 5min to solve this probelm, so really an easy one. My code runs in nearly 0 seconds.
Above two thousand people have solved this task and it’s difficulty rating is only 10%.
Someone can solve this problem easily as long as he/she knows how to calculate expectation.

Project Euler 125

Palindromic sums



This is an easy problem. My code runs in 0.045598s.
At first, I was trying to generate all the palindromic numbers and then check whether they can be formed by consecutive squares one by one. Although it yield correct answer but needs 13.xx seconds which is unbearable.
Let’s consider from another view. If we generate all possible distinct sum of consecutive squares and then check if the sum is a palindromic number and if yes, add it to our answer. Do not forget there might duplications when generate sum of consecutive squares, so I use a undered_set to mark a number as visited.