Блог пользователя arujbansal

Автор arujbansal, 2 года назад, По-английски

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!

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
2 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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