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!
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 155 |
| 2 | nik_exists | 151 |
| 3 | maspy | 149 |
| 4 | AmShZ | 145 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | BledDest | 136 |
| 8 | adamant | 135 |
| 9 | maroonrk | 132 |
| 10 | cry | 130 |
sieve[i]gives you the index of the biggest prime factor. The index is one-based.sieve[20] == 3, because20 = 2*2*5andprimes[3] == 5(5is the third prime number)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.I think you meant
prime[5] = 3, right?No,
primesis a list of primes.primes = { 0, 2, 3, 5, 7, 11, ... }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