olenihc's blog

Modified Sieve?
By olenihc, history, 8 years ago, In English

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!

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

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

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

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

        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

        → Reply