How to Code the Smallest Divisor of a Whole Number Algorithm

If you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the smallest divisor of a whole number in JavaScript and Python.

This article originally published at jarednielsen.com

How to Code the Smallest Divisor of a Whole Number

Programming is problem solving. There are four steps we need to take to solve any programming problem:

1. Understand the problem

2. Make a plan

3. Execute the plan

4. Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:

GIVEN a whole number
WHEN I request the smallest divisor
THEN I am returned a whole number greater than 1

That’s our general outline. We know our input conditions (a whole number) and our output requirements (a whole number greater than 1), and our goal is to calculate the smallest divisor.

Let’s make a plan!

Make a Plan

Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:

• Decomposition

• Pattern recognition

• Abstraction

• Algorithm

Let's use 12 as our input. You probably already know the answer, but it's a manageable number while we think through our approach and write pseudocode.

What's the smallest problem we can solve?

If our function must return a whole number greater than 1, the smallest problem can't be 1. Maybe the first thing we need to do is ensure that we don't waste time parsing a number less than or equal to 1?

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

What's our next smallest problem?

2!

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

IF n IS EQUAL TO 2
    RETURN 2;

We could proceed with this brute force approach and write a conditional for every number, but that's not how programmer's think. How can we do better?

What do we know about even numbers? Their smallest divisor is always 2! How can we adapt the pseudocode above to address this? We can use the modulo operator to check if the remainder of n divided by 2 is equal to 0:

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

ELSE IF n MOD 2 IS EQUAL TO 0
    RETURN 2;

If we were to "run" this algorithm, what numbers would be checked?

Let's map it out in a table:

What's the pattern we see?

If we map this out in a table, we can see we quickly checked more than half of the numbers in our sequence (all the even numbers plus 1), thus our remaining numbers are all odd.

Our next smallest problem is 3. We know that the smallest divisor of 3 is itself (and 1). We could set up another conditional statement checking if the remainder of n divided by 3 is equal to 0, like so...

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

ELSE IF n MOD 2 IS EQUAL TO 0
    RETURN 2;

ELSE IF n MOD 3 IS EQUAL to 0
    RETURN 3;

Looking ahead, what do we see? We would need to do the same for 5, 7, and 11. But why not 9?

Because 9 is divisible by 3.

What's the pattern established by 5, 7, and 11?

They're prime!

How do we increment by 2 with odd (prime) numbers?

We know we need to check each of the odd values, but we don't want to write a conditional for all of them.

Let's increment by 2 starting with 3.

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

ELSE IF n MOD 2 IS EQUAL TO 0
    RETURN 2;

ELSE
    SET d TO 3

    WHILE n MOD d IS NOT EQUAL to 0

        d = d + 2

        IF n MOD d IS EQUAL to 0
            RETURN d;
        ELSE
            RETURN n;

If we return n, then we know the number is prime

This is terribly inefficient, though. In a worst case scenario, we would iterate nearly half of the possiblities to return a value. How can we do better?

Let's look at our table again. Is there another pattern?

3 is a divisor of 6, 9, and 12. We already checked off 6 and 12, though. What's the relationship between 3 and 9?

3 is the square root of 9!

What's the square root of 12?

3.46410161514

If we calculate the square root of n, we can see that we quickly eliminate the need to check every odd number between 3 and n. We only need to continue iterating while d is less than the square root of n.

Let's test this assumption before we proceed. 3's and 5's are easy to work with. How about a multiple of 7? How about 77? It's the product of two prime numbers, so we won't catch it in our initial conditional statements.

The square root of 77 is 8.77496438739.

So on our first iteration, d is equal to 3.

77 is not divisible by 3 and 3 is less than 8.77496438739.

So we add 2 to 3.

77 is not divisible by 5 and 5 is less 8.77496438739.

So we add 2 to 5.

77 is divisible by 7!

Let's update our pseudocode...

INPUT n

IF n IS LESS THAN OR EQUAL TO 1
    RETURN "ENTER A NUMBER GREATER THAN 1"

ELSE IF n MOD 2 IS EQUAL TO 0
    RETURN 2;

ELSE
    SET d TO 3

    SET r TO THE SQUARE ROOT OF n

    WHILE n MOD d IS NOT EQUAL to 0 AND d IS LESS THAN r

        d = d + 2

        IF n MOD d IS EQUAL to 0
            RETURN d;
        ELSE
            RETURN n;

Execute the Plan

Now it's just a matter of translating our pseudocode into syntax. Let's start with JavaScript...

How to Code the Smallest Divisor Algorith in JavaScript

This is more or less a 1:1 translation of our pseudocode. Note that we are using the Math object and calling the sqrt() method.

const smallestDivisor = n => {
    if (n <= 1) {
        return "Enter a number greater than 1";
    } else if (n % 2 == 0) {
        return n
    } else {
        let r = Math.sqrt(n);

        let d = 3;

        while ((n % d != 0) && (d < r)) {
            d = d + 2;
        }

        if (n % d == 0) {
            return d;
        } else {
            return n;
        }
    }
}

How to Code the Smallest Divisor Algorith in Python

Unlike our JavaScript above, we need to import the math module. Otherwise, the two functions are nearly identical.

import math 

def smallest_divisor(num):
    if num <= 1:
        return "Enter a number greater than 1"
    elif num % 2 == 0: 
        return num
    else:
        r = math.sqrt(num)

        d = 3

        while num % d != 0 and d < r:
            d = d + 2

        if num % d == 0:
            return d 
        else: 
            return num

Evaluate the Plan

Can we do better?

This is pretty good. We could refactor some of the conditionals to be more concise, but at the cost of legibility without performance gain.

A is for Algorithms

Give yourself an A. Grab your copy of A is for Algorithms