Monday, September 8th, 2025¶

Last week, we looked at for loops and determining whether a given number is prime.

In [4]:
n = 15

n_is_prime = True

for d in range(2,n):
    if n % d == 0:
        n_is_prime = False
        
if n_is_prime:
    print('{} is prime.'.format(n))
else:
    print('{} is not prime.'.format(n))

15 is not prime.

Note: in the code above, it will often happen that we perform many divisibility checks for no reason (for example, if 2 divides n, then we will still unnecessarily check whether 3, 4, 5, ... also divide n). It would be helpful if we could escape the loop prematurely.

The break and continue commands¶

The break command can be used within a loop to immediately exit the loop.

In [6]:
for i in range(10):
    print(i)
    if i == 5:
        break

0
1
2
3
4
5

Exercise: Modify the prime-checking code above to exit the loop as soon as n is determined to not be prime.

In [7]:
n = 15

n_is_prime = True

for d in range(2,n):
    if n % d == 0:
        n_is_prime = False
        break
        
if n_is_prime:
    print('{} is prime.'.format(n))
else:
    print('{} is not prime.'.format(n))

15 is not prime.

Other times, we may want to immediately proceed to the next iteration of a loop. The continue command can be used to accomplish this.

In [8]:
for i in range(10):
    if i < 3:
        continue
    if i > 7:
        break
    print(i)

3
4
5
6
7

while loops¶

Suppose that we want to find the first 100 cubes that have remainder 1 after division by 4.

Problem: We don't know ahead of time how many numbers we'd have to check before we find 100 such cubes.

For these types of problems, we can use a while loop. A while loops will iteratiavely perform some operations as long as some Boolean expression is True. The syntax is as follows: while (some Boolean expression is True): (do something)

Note: the (some Boolean expression) can be (and often is) a variable that will be modified within the while loop.

In [9]:
for i in range(10):
    print(i)

0
1
2
3
4
5
6
7
8
9
In [10]:
i = 0
while i < 10:
    print(i)
    i = i + 1

0
1
2
3
4
5
6
7
8
9

We can also use break to terminate a while loop:

In [2]:
i = 0
while True:
    print(i)
    if i >= 9:
        break
    i = i + 1
    

0
1
2
3
4
5
6
7
8
9

Warnings:

  • Unlike with for loops, it is very easy to end up with a while loop that runs forever.
  • Always make sure that your Boolean expression will eventually be False so that the while loop can terminate.
  • Check that you are incrementing any necessary variables with each iteration.

If you find your code stuck running a while loop, you can hit the stop button (black square in the toolbar near the top of the notebook) to try to get Python to interrupt the kernel. If this does not work, you can restart the kernel (refresh symbol to the right of the stop button) to shut down the notebook and restart.

There are some shortcuts for incrementing variables. In particular:

  • n += 1 is equivalent to n = n + 1
  • n -= 3 is equivalent to n = n - 3
  • n *= 7 is equivalent to n = n * 7
In [3]:
n = 5
n += 1
n *= 3
print(n)

18
In [4]:
i = 0
while i < 10:
    print(i)
    i += 1

0
1
2
3
4
5
6
7
8
9

Exercise: Write code that will find the first 100 cubes that have remainder 1 after division by 4.

In [8]:
n = 1
cubes_with_remainder_1 = []

while len(cubes_with_remainder_1) < 100:
    cube = n**3
    if cube % 4 == 1:
        cubes_with_remainder_1.append(cube)
    n += 1

print(cubes_with_remainder_1)

[1, 125, 729, 2197, 4913, 9261, 15625, 24389, 35937, 50653, 68921, 91125, 117649, 148877, 185193, 226981, 274625, 328509, 389017, 456533, 531441, 614125, 704969, 804357, 912673, 1030301, 1157625, 1295029, 1442897, 1601613, 1771561, 1953125, 2146689, 2352637, 2571353, 2803221, 3048625, 3307949, 3581577, 3869893, 4173281, 4492125, 4826809, 5177717, 5545233, 5929741, 6331625, 6751269, 7189057, 7645373, 8120601, 8615125, 9129329, 9663597, 10218313, 10793861, 11390625, 12008989, 12649337, 13312053, 13997521, 14706125, 15438249, 16194277, 16974593, 17779581, 18609625, 19465109, 20346417, 21253933, 22188041, 23149125, 24137569, 25153757, 26198073, 27270901, 28372625, 29503629, 30664297, 31855013, 33076161, 34328125, 35611289, 36926037, 38272753, 39651821, 41063625, 42508549, 43986977, 45499293, 47045881, 48627125, 50243409, 51895117, 53582633, 55306341, 57066625, 58863869, 60698457, 62570773]

Exercise: Write code that will find the first 10 prime numbers.

In [10]:
primes = []

n = 2
while len(primes) < 10:
    n_is_prime = True
    for d in range(2,n):
        if n % d == 0:
            n_is_prime = False
            break
    if n_is_prime:
        primes.append(n)
    n += 1
print(primes)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Functions in Python¶

Very often, we want to write code that can be applied to many different inputs. We can accomplish this by writing a Python function. The syntax for defining functions in Python is: def function_name(some_inputs): ...do something...

In [11]:
def hello_world():
    print('Hello world!')

After defining a function, we can call upon it to execute the function's code.

In [13]:
hello_world()
hello_world()
hello_world()

Hello world!
Hello world!
Hello world!

Exercise: Write a function called is_prime that takes in a variable n and prints whether or not n is prime.

In [14]:
def 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:
        print('{} is prime.'.format(n))
    else:
        print('{} is not prime.'.format(n))
In [16]:
for n in range(2,20):
    is_prime(n)

2 is prime.
3 is prime.
4 is not prime.
5 is prime.
6 is not prime.
7 is prime.
8 is not prime.
9 is not prime.
10 is not prime.
11 is prime.
12 is not prime.
13 is prime.
14 is not prime.
15 is not prime.
16 is not prime.
17 is prime.
18 is not prime.
19 is prime.

It is often more useful to have functions like the above return either a True or a False Boolean depending on whether n is prime or not.

More generally, we often want functions to return some value to the caller. This can be done using a return statement:

Exercise: Rewrite the is_prime function to return a Boolean True if the input is prime and False if not.

In [17]:
def 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
In [21]:
for n in range(2,20):
    #print(n, is_prime(n))
    if is_prime(n):
        print('{} is prime.'.format(n))
    else:
        print('{} is not prime.'.format(n))

2 is prime.
3 is prime.
4 is not prime.
5 is prime.
6 is not prime.
7 is prime.
8 is not prime.
9 is not prime.
10 is not prime.
11 is prime.
12 is not prime.
13 is prime.
14 is not prime.
15 is not prime.
16 is not prime.
17 is prime.
18 is not prime.
19 is prime.

Let's use our is_prime function to modify our previous while loop that searched for primes.

In [24]:
primes = []

n = 2
while len(primes) < 10:
    if is_prime(n):
        primes.append(n)
    n += 1
print(primes)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Note: Variables that are defined within a function only exist within that function. In the above example, we've defined n_is_prime within the is_prime function. This is a completely different variable to the globally defined variable n_is_prime that was defined at the top of this notebook. If a function calls upon a variable name that it has not defined, it will look outside the function for that variable name.

In [25]:
def test_function():
    hello_this_is_a_test = 'MTH 337'
    print(hello_this_is_a_test)
In [26]:
test_function()

MTH 337
In [27]:
print(hello_this_is_a_test)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[27], line 1
----> 1 print(hello_this_is_a_test)

NameError: name 'hello_this_is_a_test' is not defined
In [28]:
this_is_a_second_test = 'Hello'

def test_function():
    print(this_is_a_second_test)
In [29]:
test_function()

Hello
In [30]:
this_is_a_third_test = 'Hello'

def test_function():
    this_is_a_third_test = 'Goodbye'
In [31]:
test_function()
print(this_is_a_third_test)

Hello

Note: A function will terminate as soon as it hits a return statement.

In [32]:
def test_function():
    print('Hello')
    return 5
    print('Goodbye')
In [33]:
test_function()

Hello
Out[33]:
5

Exercise: Write a function get_primes that takes in an input n and returns a list of all prime numbers between 2 and n (inclusively).

In [ ]:

Modules in Python¶

When starting a Jupyter notebook, Python loads in a base set of commands that are made available (e.g. print, list, int, etc.). However, there are many other commands that are not loaded by default that we sometimes want to make use of. We can import various modules that contain all kinds of additional functionality.

For example, suppose we want to consider the efficiency of our get_primes function. We can import the time module to gain access to different time-related tools, which we can use to time our function.

Importing a module¶

We can use the syntax import <some module> to make that module available to us. After doing so, we can use the syntax <some module>.<some function or object> to call upon variables functions or objects contained in that module.

In [34]:
import time
In [36]:
time.asctime()
Out[36]:
'Mon Sep  8 16:28:25 2025'

We can use the time function from the time module to time our get_primes function.

In [37]:
time.time()
Out[37]:
1757363340.2630873
In [38]:
t0 = time.time()
In [39]:
t1 = time.time()
In [40]:
print(t1 - t0)

15.103442668914795

Importing from a module¶

Sometimes we just want to make use of a single function or object from within a module. We can use the syntax from <some module> import <some function or object> to gain direct access to the function or object. After doing so, we can simply use <some function or object> directly rather than looking back inside the module (that is, we do not need to include <some module>. before calling upon the function/object).

In [41]:
asctime()

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
Cell In[41], line 1
----> 1 asctime()

NameError: name 'asctime' is not defined
In [42]:
time.asctime()
Out[42]:
'Mon Sep  8 16:36:18 2025'
In [43]:
from time import asctime
In [44]:
asctime()
Out[44]:
'Mon Sep  8 16:36:37 2025'

Optimization¶

Let's think of ways that we can improve the efficiency of our get_primes function. By extension, we will want to improve the efficiency of our is_prime function.

In [ ]:
def 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
In [57]:
n = 1000000007

t0 = time.time()
print(is_prime(n))
t1 = time.time()
print(t1-t0)

True
65.03244352340698

We can import the sqrt function from the math module in order to compute square roots.

Exercise: Rewrite the is_prime function to take advantage of the $\sqrt{n}$ optimization that we've discussed.

In [58]:
from math import sqrt
In [63]:
def new_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
In [65]:
n = 1000000007

t0 = time.time()
print(new_is_prime(n))
t1 = time.time()
print(t1-t0)

True
0.006369113922119141

Exercise: Compare the efficiency of using this optimization by timing the old version of is_prime against the new version.

In [ ]: