Free lessonsMath and bits · Stage 0 · Digits and divisibility · Step 3

Divisors come in pairs

Count divisors by checking only up to the square root. About 9 minutes.

Divides means no remainder

Does 4 divide 36? Yes: share 36 sweets among groups of 4 and nothing is left over, so the remainder is 0. That is all "divides" means.

The lazy way is to test every number from 1 up to n. For n near a trillion that is a trillion checks, hours of running, so we need something smarter.

Remainder 0: means the number divides evenly.

In code

36 % 4   # 0, so 4 divides 36
36 % 5   # 1, so 5 does not

n = 36 · try i while i × i ≤ 36

count: 2
found: 1, 36

36 % 1 = 0. A hit, and it brings its partner 36 ÷ 1 = 36. Two divisors.

Move 1 of 6

Every small divisor has a big partner

Divisors come in pairs. Since 4 divides 36, so does 36 ÷ 4 = 9. For 36 the pairs are 1 and 36, 2 and 18, 3 and 12, 4 and 9, and 6 with itself.

Each pair has one member no bigger than the square root, so you only test numbers while their square stays within n, and every hit counts for two.

Stop: once the number times itself passes n. No square roots needed.

When the number times itself equals n: the pair is one number. Count it once.

In code

count = 0
i = 1
while i * i <= n:
    if n % i == 0:
        count += 1 if i * i == n else 2
    i += 1
return count

Quick check

Checking i from 1 while i × i ≤ 36, which i values are hits, and how many divisors does 36 have?

hits: 1, 2, 3, 4, 6

Show the answer

9. 1, 2, 3 and 4 each bring a partner (8 divisors), and 6 pairs with itself (1 more).

Your problem

Count the divisors

Return how many whole numbers divide n with no remainder, including 1 and n itself. n can be as large as a trillion, so trying every number up to n will be too slow.

Example

n = 12 → 6

1 ≤ n ≤ 1,000,000,000,000 (use a long)

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding