Using Counters in Loops

A divisor leaves a remainder of zero when N is divided by that candidate.

Programming

Predicting a Count Before Running the Loop

A counter is a variable whose job is to keep track of how many times something happened while a loop runs. Counting divisors is a practical way to use a for loop for more than simple repetition. The algorithm receives a positive integer N, examines every candidate from 1 through N, and counts the candidates that divide N with no remainder. In this article you will follow that process one candidate at a time.

What do you think happens?

For N = 6, how many of the candidates 1, 2, 3, 4, 5, and 6 divide 6 with no remainder?

Reveal answer

Answer:

The candidates 1, 2, 3, and 6 each leave a remainder of zero when 6 is divided by them. The candidates 4 and 5 leave remainders of 2 and 1, so they are tested but not counted.

Notice that the final number is only part of the answer. The more useful prediction is which exact candidates cause the count to go up. If the final count turns out to be wrong, you can compare the candidates you expected to be counted with the candidates the program actually counted, and that comparison shows where the mistake started.

Testing a Candidate With N % D

Definition

A divisor leaves a remainder of zero when N is divided by that candidate. For a positive integer N and a candidate D, D is a divisor of N when dividing N by D produces no remainder.

In Python, the percent sign is the remainder operator. The expression N % D gives the amount left over after N is divided by D as evenly as possible. When that leftover is zero, D splits N into equal groups with nothing remaining. When the leftover is anything other than zero, D does not divide N evenly, so the candidate fails the test.

How does computing N % D produce a remainder, and what does the result tell us about whether D divides N?

Read the diagram from left to right. The value 6 is the number being tested, the percent sign asks for the remainder, and 4 is the candidate. The result is 2, which is not zero, so 4 is not a divisor of 6. Any candidate whose result is zero passes the test instead.

Tracing Every Candidate for N = 6

The counting algorithm does not try to guess which candidates are divisors. It tests every candidate from 1 through N, in order. For N = 6, that means the loop visits D = 1, then D = 2, and continues until D = 6. Each visit runs the same remainder test, and only the candidates that pass increase the count.

In what order does the loop visit candidates 1 through 6, and which candidates leave a remainder of zero when 6 is divided by them?

Worked example

Tracing the Divisor Count for N = 6

Starting with divisorCount at 0, test each candidate D from 1 through 6 using the remainder 6 % D, and report the final count.

1
D = 1
6 % 1 leaves a remainder of 0, so the test succeeds and divisorCount goes from 0 to 1.
2
D = 2
6 % 2 leaves a remainder of 0, so divisorCount goes from 1 to 2.
3
D = 3
6 % 3 leaves a remainder of 0, so divisorCount goes from 2 to 3.
4
D = 4
6 % 4 leaves a remainder of 2. The candidate is tested but fails, so divisorCount stays at 3.
5
D = 5
6 % 5 leaves a remainder of 1. The candidate fails, so divisorCount stays at 3.
6
D = 6
6 % 6 leaves a remainder of 0, so divisorCount goes from 3 to 4.

Result

The final divisorCount is 4. The counted candidates are 1, 2, 3, and 6.

When the Counter Changes

The counter changes only at the successful test. A candidate that fails the remainder test still belongs to the loop's range, so the loop visits it, but it does not increase divisorCount. The loop always runs through every candidate from 1 through N, and the counter is the only thing that records which candidates passed.

python

def count_divisors(n):
    divisorCount = 0
    for d in range(1, n + 1):
        if n % d == 0:
            divisorCount += 1
    return divisorCount

print(count_divisors(6))

def count_divisors(n):
    divisorCount = 0
    for d in range(1, n + 1):
        if n % d == 0:
            divisorCount += 1
    return divisorCount

print(count_divisors(6))

Output (expected)

Notes on the code

divisorCount starts at 0 before the loop begins
range(1, n + 1) produces every candidate from 1 through N
The remainder test n % d == 0 decides whether the counter changes
divisorCount += 1 runs only when the test succeeds

How does the value of divisorCount change from one candidate to the next, and at which candidates does it increase?

Where a Wrong Count Comes From

When a divisor count comes out wrong, the mistake almost always lives in the single decision made on each iteration. Tracing the candidates in order helps reveal the exact point where an incorrect result begins, because you can check each step's remainder against the counter's value.

Common mistake
Incrementing the counter for every candidate
What it looks like
Adding 1 to divisorCount on every pass through the loop would count all six candidates for N = 6 and report 6.
Why it fails
The count changes only when the divisor test succeeds. A candidate that fails the remainder test belongs to the loop's range but must not increase the counter.
Do this instead
Place the increment inside the branch that checks whether n % d is zero.
Common mistake
Skipping a true divisor
What it looks like
If the loop ran only from 1 through N minus 1, the candidate 6 would never be tested for N = 6, and the count would be 3 instead of 4.
Why it fails
Every candidate from 1 through N must be examined, and N itself is a divisor of N.
Do this instead
Make sure the loop's upper bound includes N, as range(1, n + 1) does.
Common mistake
Testing the wrong pair of values
What it looks like
Writing D % N instead of N % D tests the wrong relationship between the two numbers.
Why it fails
The remainder test asks whether D divides N, so N is the value being divided and D is the candidate.
Common mistake
Checking the final count only

The last item in the list above deserves attention. If you only compare the final number with the expected answer, you cannot tell which candidate caused the error. A better habit is to list the candidates that should be counted, then check whether each one actually incremented divisorCount during the trace.

Trace the Loop for N = 8

EASY

Trace the algorithm for N = 8. List every candidate D from 1 through 8 that makes 8 % D equal to zero, then state the final value of divisorCount. Before you begin, predict which candidates will be counted.

Hints

Compute 8 % D for each candidate in order, starting at D = 1.
A candidate is counted only when the remainder is exactly zero.
Check whether N itself, here 8, passes the test.

Your attempt (not saved)

Key Takeaways

A divisor of N is a candidate D that leaves a remainder of zero when N is divided by D, which the expression N % D tests.
The counting algorithm examines every candidate from 1 through N, so the loop range must include N itself.
The counter changes only when the remainder test succeeds; candidates that fail are visited but not counted.
A wrong final count can be located by comparing the candidates that should be counted with the candidates that actually incremented the counter during the trace.