Wednesday, September 10th, 2025

Last time we defined a function is_prime that took in an integer n and returned True if n was prime and false if not.

from math import sqrt

def is_prime(n):
    n_is_prime = True

    for d in range(2,int(sqrt(n))+1):
        if n % d == 0:
            n_is_prime = False
            break
            
    if n_is_prime:
        return True
    else:
        return False

Note: we made the optimization of only checking for divisors $d$ up to $\sqrt{n}$, which provided a massive improvement in speed. We used the time function from the time module to measure the effect of this optimization.

def old_is_prime(n):
    n_is_prime = True

    for d in range(2,n):
        if n % d == 0:
            n_is_prime = False
            break
            
    if n_is_prime:
        return True
    else:
        return False

import time

n = 1000000007

t0 = time.time()
old_is_prime(n)
t1 = time.time()
print('old_is_prime({}) took {} seconds'.format(n,t1-t0))

t0 = time.time()
is_prime(n)
t1 = time.time()
print('is_prime({}) took {} seconds'.format(n,t1-t0))

old_is_prime(1000000007) took 69.81820678710938 seconds
is_prime(1000000007) took 0.0019218921661376953 seconds

Logical operators: not, and, or

We can invert and/or combine Boolean expressions using the operators not, and, and or. For example:

• not <some Boolean expression> will be True when <some Boolean expression> is False.
• <Boolean expression 1> and <Boolean expression 2> will be True when <Boolean expression 1> and <Boolean expression 2> are both True.
• <Boolean expression 1> or <Boolean expression 2> will be True when at least one of <Boolean expression 1> and <Boolean expression 2> are True.

Exercise: We say that two primes $p$ and $q$ are twin primes if they differ by $2$. Write code that will find all twin primes with $p, q \leq 10,000$.

twin_primes = []

for p in range(2,10000 - 1):
    q = p+2
    if is_prime(p) and is_prime(q):
        twin_primes.append([p,q])

twin_primes[20]

[347, 349]

When looking for numbers with a certain property, it can be useful to write a function that identifies when they have this property (e.g. the is_prime function tests for primality).

def is_twin_prime(p,q):
    if is_prime(p) and is_prime(q) and abs(p - q) == 2:
        return True
    else:
        return False

is_twin_prime(5,7)

True

twin_primes = []

for p in range(2,10000 - 1):
    q = p+2
    if is_twin_prime(p,q):
        twin_primes.append([p,q])

Exercise: Write code that will find all positive integers less than $10,000$ that are either a perfect square or a perfect cube.

Testing an integer to check if it is a perfect square:

n = 49
sqrt_n = n**(1/2)

if int(sqrt_n) == sqrt_n:
    print('{} is a perfect square.'.format(n))
else:
    print('{} is not a perfect square.'.format(n))

49 is a perfect square.

Let's create a function that performs this check:

def is_square(n):
    sqrt_n = n**(1/2)
    if int(sqrt_n) == sqrt_n:
        return True
    else:
        return False

print(is_square(49))
print(is_square(55))

True
False

We can similarly create a function to check for perfect cubes:

def is_cube(n):
    cbrt_n = n**(1/3)
    if int(cbrt_n) == cbrt_n:
        return True
    else:
        return False

print(is_cube(8))
print(is_cube(9))

True
False

Note: we saw (for some people) that working floating points allows for inprecision. It might be safer to round the floats instead of using int.

def is_cube(n):
    cbrt_n = n**(1/3)
    if round(cbrt_n) == cbrt_n:
        return True
    else:
        return False

We're still working with floating point comparisons, because cbrt_n is a float.

def is_cube(n):
    cbrt_n = n**(1/3)
    if round(cbrt_n)**3 == n:
        return True
    else:
        return False

is_cube(125)

True

Note: our is_square and is_cube functions are nearly identical. Can we write a single function, say is_root that can handle both cases?

def is_power(n,power):
    root_n = n**(1/power)
    if round(root_n)**power == n:
        return True
    else:
        return False

is_power(225,2)

True

is_power(125,3)

True

Now we can find integers that are either a perfect square or a perfect cube:

squares_or_cubes = []
for n in range(10000+1):
    if is_root(n,2) or is_root(n,3):
        squares_or_cubes.append(n)

squares_or_cubes[100]

7225

We can also find numbers that are both squares and cubes:

squares_and_cubes = []
for n in range(10000+1):
    if is_root(n,2) and is_root(n,3):
        squares_and_cubes.append(n)

squares_and_cubes

[0, 1, 64, 729, 4096]

Documenting your code

When writing reports for this class (and when coding in general), it is important to explain your code to a potential reader so that they can follow along and understand what the code is doing and how it works. With Jupyter notebook, we have two main tools for documenting our code:

• Writing explanations in Markdown cells that preceed each code cell;
• Writing code comments directly within code cells.

Note: We will use both tools for every bit of code in our projects.

Code comments

To add a comment within a code cell, we simply write a hashtag # followed by whatever text we want to include. Python will ignore anything that comes after the hashtag.

print('Hello') # This is a comment. Python ignores anything after the hashtag
print(1+2+3)
# print(3+4+5)

Hello
6

Exercise: Add code comments to the is_prime function to explain how the function works.

def is_prime(n):                             # Define a function is_prime
    n_is_prime = True                        # Define a Boolean that is True when n is 
                                             # prime, false otherwise. We will assume that
                                             # n is prime unless we can show otherwise

    for d in range(2,int(sqrt(n))+1):        # Loop through possible divisors d
        if n % d == 0:                       # Check if n is divisble by d
            n_is_prime = False               # If so, then n is not prime...
            break                            # ... and we can stop looking for divisors
            
    if n_is_prime:                           # If no divisor was found, then n must be prime
        return True
    else:                                    # Otherwise, a divisor was found and n is not prime
        return False

We should still provide an explanation for why we only need to check divisors up to the square root, rather than all the way up to n. I would recommend giving this explanation in a markdown cell just prior to defining the function.

Markdown: Code references

When explaining bits of Python code in Markdown cells, we will often want to refer to explicit bits of Python code (e.g. function names, variable names, specific lines, etc.). When doing so, we can use the backtick key ` (found above TAB, shared by the ~ symbol) to surround bits of Python code.

For example, the Markdown `is_prime` will be rendered as is_prime. Notice that the text is in a uniform-spaced font (each character has the same width) and has a light-gray background. This should always be done when references bits of Python code in your reports.

Markdown: LaTeX

We will also often want to refer to various math equations or expressions in our projects. LaTeX is a tool for writing such math expressions. To enter LaTeX mode in a Markdown cell, we use dollar signs $.

• Plain-text:
  • 123456
  • 123^456
  • 123_456
• LaTeX:
  • $123456$
  • $123^{456}$
  • $123_{456}$

Some common LaTeX commands:

• Exponents: $x^2 + y^2$ renders as $x^2 + y^2$.
• Fractions: $\frac{numerator}{denominator}$ renders as $\frac{numerator}{denominator}$.
• Integrals and trig functions: $\int_0^x \cos(t) dt$ renders as $\int_0^x \cos(t) dt$.

Using a single dollar sign writes LaTeX in in-line mode (i.e. will appear within the same lines as the surrounding text). We can use two dollar signs ($$) to write in display mode, which gives a centered equation. For example, $$\int_0^x \cos(t) dt$$ renders as $$\int_0^x \cos(t) dt$$

whereas $\int_0^x \cos(t) dt$ renders as $\int_0^x \cos(t) dt$.

Other common LaTeX commands:

• Subscripts and superscripts: $a_n$, $2^n$ renders as $a_n$, $2^n$.
• Square roots and other roots: $\sqrt{7}$, $\sqrt[10]{x^2-5}$ renders as $\sqrt{7}$, $\sqrt[10]{x^2 - 5}$.
• Greek letters: $\alpha$, $\beta$, $\gamma$, $\sigma$, $\omega$, $\pi$ renders as $\alpha$, $\beta$, $\gamma$, $\sigma$, $\omega$, $\pi$.

Example: Euler's formula: $$e^{i\pi} + 1 = 0$$

Pythagorean theorem: $$\cos^2 \theta + \sin^2\theta = 1$$

We can have LaTeX automatically adjust the size of parentheses using \left( and \right). For example, $$\left(\frac{1}{2} + 4\right)$$ renders as:

$$\left(\frac{1}{2} + 4\right)$$

whereas $$(\frac{1}{2} + 4)$$ renders as

$$(\frac{1}{2} + 4).$$

We will regularly use LaTeX in our project reports whenever referring to math equations or variables.

Exercise: Using Markdown and LaTeX, write out a definition of a prime number.

We say a positive integer $p>1$ is a prime number if the only positive integer divisors are $1$ and itself.

Exercise: Using Markdown and LaTeX, explain what the is_prime function does and how it works.