All Divisors of Number
Only check up to sqrt(n), pair each divisor with n/i
time O(sqrt(n))space O(d)
Divisors come in pairs (i, n/i), so it's only necessary to check i up to sqrt(n) — every divisor above that has already been found as the paired n/i of a smaller one.
Only check up to sqrt(n), pair each divisor with n/i
step 1 / 8
sqrt(36) = 6, so check i from 1 to 6 — every divisor beyond that already appeared as a pair.
Pseudocode
1FUNCTION printDivisors(n):2 make an empty list of divisors3 FOR i from 1 to sqrt(n):4 IF n is divisible by i:5 add i and n/i to the list (just once if they are equal)6 RETURN the divisors in sorted order
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- sqrt(36) = 6, so check i from 1 to 6 — every divisor beyond that already appeared as a pair.
- i=1: 36 % 1 === 0. Divisors: 1 and 36/1 = 36.
- i=2: 36 % 2 === 0. Divisors: 2 and 18.
- i=3: 36 % 3 === 0. Divisors: 3 and 12.
- i=4: 36 % 4 === 0. Divisors: 4 and 9.
- i=5: 36 % 5 !== 0 — not a divisor, skip.
- i=6: 36 % 6 === 0. Since i === n/i (6 === 6), add divisor 6 only once.
- Sorted, the divisors of 36 are [1,2,3,4,6,9,12,18,36] — 9 divisors total.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.