Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Modified Sieve?
Автор olenihc, история, 8 лет назад, По-английски

Hi!

I've come across this piece of code of a (modified?) sieve and I'm trying to figure out what sieve[i] means and how it works, specially the 2nd for.

Would you help me, please?

Thanks!

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

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

sieve[i] gives you the index of the biggest prime factor. The index is one-based.

sieve[20] == 3, because 20 = 2*2*5 and primes[3] == 5 (5 is the third prime number)

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Using this method, you generate the prime factorization pretty quick. You can find the biggest prime number using the sieve, divide by this number and repeat with the result.

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

    I think you meant prime[5] = 3, right?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      No, primes is a list of primes. primes = { 0, 2, 3, 5, 7, 11, ... }

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

        Ah, sorry I totally misunderstood.

        I thought you meant to give another example, which is sieve[5] = 3, and didn't notice the difference in arrays' names. Sorry about that :D

        → Ответить