| 1 | vi divisor_sieve(int n) { |
| 2 | vi mnd(n+1, 2), ps; |
| 3 | if (n >= 2) ps.push_back(2); |
| 4 | mnd[0] = 0; |
| 5 | for (int k = 1; k <= n; k += 2) mnd[k] = k; |
| 6 | for (int k = 3; k <= n; k += 2) { |
| 7 | if (mnd[k] == k) ps.push_back(k); |
| 8 | rep(i,1,size(ps)) |
| 9 | if (ps[i] > mnd[k] || ps[i]*k > n) break; |
| 10 | else mnd[ps[i]*k] = ps[i]; } |
| 11 | return ps; } |
| 12 | // vim: cc=60 ts=2 sts=2 sw=2: |