Count Divisors of Every Number up to N (Sieve style)

MEDIUM-HARD · C · 3000ms

For a number-theory poster, Farhan wants the divisor count of EVERY integer from 1 to N, computed efficiently with a sieve-style approach rather than one-by-one factorization. Read N. For every integer from 1 to N, compute the number of divisors it has, using a sieve-like O(N log N) approach (do NOT check each number individually in O(sqrt(i)) — that's also acceptable but the sieve approach is the intended lesson). Print the divisor counts space-separated.

Input

One integer N.

Output

N integers: divisor counts for 1..N.

Constraints

1 ≤ N ≤ 10^6

Sample Input

Sample Output

1 2 2 3 2 4

← Prev Next →

main.c

Loading editor…

Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.