Day 1

I want to start a challenge for myself to see if I can learn some algorithm(or math theorem, programming tricks) every day, what will I become several months later. A difficult level (for me) of one to five star is labeled next to the header. The blogs serves mainly as a reminder for myself, so it might seems unclear for someone at the first sight of the algorithm. So again, it’s only for my reference.

Let’s spare cliche and start digging.

Sieve of Eratosthenes *

The algorithm serves to find all prime numbers among a range. The idea is to have an unmarked array of numbers, iterate from the start to the end. When met with an unmarked number, iterate from this number to the end and filter out the multiples of this number(depending on your purposes, you can either delete it or marked it). Repeat this process till the end.

There exists an optimization. Instead of iterating all numbers in the array, we can stop once the number is larger than sqrt(last_num). That’s because there is an implicit optimization here: everytime we filter an array, we are actually starting at the square of this number, because we’ve already filtered out previous numbers. For example, for a range of 2 to 100, when we encounter the number 5, we don’t have to examine 5 * 4, 5 * 3, 5 * 2, because they have already been wiped out.

//pseudocode
for number[0] to number[sqrt(last_num)]
    if the number is unmarked
      filter out the multiple of this_num

After this process the array should only be left with prime numbers. As for the time complexity, initially I think it is Xn². X is smaller than 1, obviously, but to what extent? I’ve no idea. So I search online again.

After reading some wikipedia and stackoverflow I find the complexity is actually O(nloglogn). As for why I give up. Too many explanations I don’t know what they are talking about.

GCD/GCF **

I have met this algorithm a while ago when I was working on Leetcode. I remember me searching a few tutorials and understand how and why it works. Yet a month later I found myself forgetting the why and how again. But luckily this time I find a visual representation of the algorithm rather a rigorous proof. That is much easier to understand and remember. Here is the link:

https://medium.com/i-math/why-does-the-euclidean-algorithm-work-aaf43bd3288e#.pzda7dg7i

I write code for it:

//in javascript. a < b.
function eg(a, b) {
   if (a === 0) { return b; }
   return eg(b % a, a);
}

LCM **

Following GCD is LCM. There are plenty of ways to get LCM and here is the most efficient one I’ve found. For two numbers a and b,

LCM = a * b / GCD(a,b)

It seems unintuitive to me at first. Actually, under the hood it just means 1. breaking the numbers in to multiples of prime numbers; 2. multiply every such number; 3. divide it by the common prime numbers a and b share, so that the GCD is not multiplied twice.

I don’t think I can understand what I said above without the following Venn Diagram. Oh, it’s the second time today that I found a diagram can be so useful!

Nice!