TT1–TT3 - Programs and prime factorisation | OCR A-Level Further Mathematics B (MEI)

Write, trace and refine short number-theory programs. Use conditions, loops, functions, local and global variables, input and output; build a reliable prime test and use unique prime factorisation.

Tell the program what counts

A program announces that $1$ is prime. Has the computer discovered new mathematics, or have we missed a condition?

The computer has followed its instructions. To make a useful mathematical program, specify the domain, the test and what the output means.

You already know

A prime is an integer greater than $1$ with exactly two positive divisors. Divisibility means an integer remainder of zero. Earlier mathematics used algorithms; here we write their steps explicitly in Python.

The name on the left of = stores a value. input() reads text, so int() converts integer text into an integer value. print() displays a result. An if condition chooses a branch; indentation identifies the statements inside it.

Conditions and integer arithmetic

In Python, n % d is the remainder when integer n is divided by positive integer d. Use == to test equality, rather than the assignment symbol =. The condition n % d == 0 tests whether d divides n.

Start with a domain check. Passing it makes a number a candidate for testing, not a proved prime.

Worked example 1: a number inside the domain

Question. Trace this program for input 15.

Python

n = int(input("Integer n: "))
if n < 2:
    print("Not prime")
else:
    print("Candidate for a prime test")

Plan. Convert the input, evaluate the comparison, then follow exactly one branch.

Step	Result	Reason
Convert input	`n = 15`	Store an integer.
Test `n < 2`	`False`	$15>2$ .
Follow `else`	`Candidate for a prime test`	The domain check passed.

Why this step? “Candidate” does not assert primality: $15$ still needs a divisor test.

Answer. The output is Candidate for a prime test.

Check. $15=3\times5$ , so calling it prime here would be wrong.

Change only the input to 1. The same comparison must select the other branch.

Worked example 2: excluding one

Question. Trace the same program for input 1.

Python

n = int(input("Integer n: "))
if n < 2:
    print("Not prime")
else:
    print("Candidate for a prime test")

Plan. Repeat the conversion and condition check.

Step	Result
Convert input	`n = 1`
Test `n < 2`	`True`
Execute first branch	`Not prime`

Why this step? The definition's “greater than $1$ ” requirement must be encoded; a later divisor loop may have no iterations for $1$ .

Answer. The output is Not prime.

Check. Zero and negative integers take this branch too. Non-integer text is outside this short program's input contract.

Programming syntax is not supplied in the formula booklet. The mathematical definition determines the correct condition.

Watch out

Wrong: treat any positive integer as a possible prime. Right: exclude integers below $2$ , and reserve a prime verdict until the divisor test succeeds.

Write a domain check with new messages.

Check a whole range

A loop repeats a test for successive candidates. An accumulator remembers a running count or total.

In Python, range(1, n + 1) supplies integers $1$ through $n$ . Its stopping value is excluded, which is why the + 1 matters. Initialise the accumulator before the loop; update it only when the condition holds.

Worked example 3: counting divisors

Question. Determine the output for n = 12.

Python

n = 12
count = 0
for d in range(1, n + 1):
    if n % d == 0:
        count = count + 1
print(count)

Plan. List candidates satisfying the condition and count the updates.

Successful `d`	$1$	$2$	$3$	$4$	$6$	$12$
Updated `count`	$1$	$2$	$3$	$4$	$5$	$6$

Why this step? The loop visits every candidate, but the counter changes only at actual divisors.

Answer. The output is 6.

Check. The factor pairs $(1,12),(2,6),(3,4)$ account for all six divisors.

Change only n to 13. The endpoint is now a prime.

Worked example 4: two successful tests

Question. Trace this divisor count.

Python

n = 13
count = 0
for d in range(1, n + 1):
    if n % d == 0:
        count = count + 1
print(count)

Plan. Find successful candidates, keeping the upper endpoint.

Successful `d`	$1$	$13$
Updated `count`	$1$	$2$

Why this step? range(1, n) would miss $n$ itself and report only one divisor of a prime.

Answer. The program displays 2.

Check. Candidates $2$ through $12$ all leave non-zero remainders.

Changing an update from count + 1 to total + d changes counting divisors into adding them.

Watch out

Wrong: reset the accumulator inside the loop. Right: initialise it once before the loop so earlier successes are remembered.

Use a sum in place of a count.

Keep each calculation's variables local

A function packages an algorithm for calls with different arguments. return passes a value back to its caller; it differs from displaying a value with print.

Local and global variables

A variable assigned inside a function, including a parameter, is local unless explicitly declared otherwise. A variable assigned at the outer program level is global. The same spelling can name different variables in different scopes.

Each call below gets a fresh local counter. Its parameter receives the argument's value without overwriting a global variable.

Worked example 5: a local counter

Question. Determine all three printed lines.

Python

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

n = 12
count = 100
result = divisor_count(10)
print(result)
print(n)
print(count)

Plan. Trace local variables, then return to the unchanged outer variables.

Stage	Local state	Outer state
Enter function	`n = 10`, `count = 0`	`n = 12`, `count = 100`
Find divisors $1,2,5,10$	`count = 4`	Unchanged
Return	Pass $4$ to caller	`result = 4`

Why this step? The local count is distinct from the global count.

Answer. The lines are 4, 12, 100.

Check. The local parameter was $10$ ; no assignment changed the global n.

Change only the call's argument from 10 to 13.

Worked example 6: fresh state for another call

Question. Determine this program's output.

Python

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

n = 12
count = 100
result = divisor_count(13)
print(result)
print(n)
print(count)

Plan. Count the argument's divisors, then inspect the globals separately.

Quantity	Value
Local parameter	$13$
Local counter returned	$2$
Global `n`	$12$
Global `count`	$100$

Why this step? A new call starts its own counter at zero, not at the preceding call's final count.

Answer. The lines are 2, 12, 100.

Check. $13$ has two positive divisors; both outer assignments remain unchanged.

A function can read an unshadowed global name. A global declaration can make an assignment affect that outer name, but none is needed here. Passing inputs and returning results makes a mathematical calculation's dependencies explicit and easier to test.

Watch out

Wrong: expect a local assignment to update a same-named global. Right: distinguish the scopes and use the returned result.

Trace the same boundary with new data.

A return belongs in the right place

One divisor proves a number composite. One non-divisor does not prove it prime: every required candidate must first be eliminated.

This basic routine accepts integers. For $n\ge2$ , it tests proper divisor candidates $2$ through $n-1$ .

Python

def is_prime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

The final return True is outside the loop. For $n=2$ , the loop is empty: the domain check and absence of possible proper divisors make True correct.

Worked example 7: exhaust the candidates

Question. Trace is_prime(7) using this routine.

Plan. Pass the guard and inspect every required candidate before accepting.

`d`	$2$	$3$	$4$	$5$	$6$
`7 % d`	$1$	$1$	$3$	$2$	$1$

The loop ends without a zero remainder; the function then returns True.

Why this step? Accepting after the first non-divisor would wrongly accept some composite numbers.

Answer. True, after five remainder tests.

Check. $7$ has only the positive divisors $1$ and $7$ .

Change only the argument to the square $9$ .

Worked example 8: stop at a divisor

Question. Trace is_prime(9).

Plan. Stop at the first zero remainder.

`d`	Remainder	Action
$2$	$1$	Continue
$3$	$0$	Return `False`

Why this step? return exits the whole function; candidates $4$ through $8$ are never tested.

Answer. False, after two remainder tests.

Check. $9=3^2$ : a square-root divisor must be included.

Predict all four lines, run the program, then replace 29 by 49 in the list. Predict the changed line before running again.

Continue this lesson.

You’re previewing NovaLearn without an account. Create a free account to read the rest.

Create free account

Last Accessed

Core Pure

Mechanics (Major and Minor)

Statistics (Major and Minor)

Modelling with Algorithms

Numerical Methods

Extra Pure

Further Pure with Technology

TT1–TT3 - Programs and prime factorisation

Tell the program what counts

Check a whole range

Keep each calculation's variables local

A return belongs in the right place

Continue this lesson.

Learn faster with Nova