Project Euler 323

Bitwise-OR operations on random integers

This is a quite simple problem about probability but it costs me 20 minutes to varify the correctness of my method. Fortunately, I got Accepted at the first try. BTW, my code runs in about 0 seconds(cuz time complexity is O(32 * 32)). As described, every integer in this sequence are independent and their possibility to be a specific integer are equal. Assuming that we already collect i bits out of 32 bits then we take another integer from the sequence and how many different kind of bits we can get now. It’s simple to figure out the fomula.

Project Euler 179

Consecutive positive divisors

As we only need calculate the number of divisors for integers 1 < n < 10^7, It says possible to bruteforce whose running time is $O(n \times \sqrt{n})$. Of course this method is far from satisfy. My code runs in 0.869 seconds. The insights is that for every number n we have $n = p_1^{m_1} \times p_2^{m_2} \times … \times p_i^{m_i}$ and the number of factors of n is $m_1 \times m_2 \times … \times m_i$.

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 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.