arujbansal's blog

[Video Tutorial] Sieve of Eratosthenes
By arujbansal, 2 years ago, In English

Hi,
I recently posted a tutorial on the Sieve of Eratosthenes. Participants with less experience consider it to be a tool for prime factorisation/computing primes, but the general idea of "iterating over multiples" can be very powerful and I will make follow-up videos on some of the following problems, which don't really have anything to do with primes:

Video Link: Click Here

Subscribe to the channel to see more tutorials!

  • Vote: I like it
  • +16
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Nice tutorial! The idea of "iterating over multiples" used in number theory problems is very closely related to the Mobius function, and it becomes clearer when you consider the Mobius function of an arbitrary poset. In that context, iterating over multiples becomes iterating over reachable vertices in the DAG of the poset (or elements that are greater than or equal to the element under consideration under the ordering of the poset).

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you! Yeah, the idea of "iterating over multiples" has also appeared a lot in recent contests.

    → Reply