Wednesday, September 16th 2026¶
On Monday, we talked about documenting our code with both Markdown explanations and accompanying code comments. We also started looking at our first project.
Our first project deals with prime numbers and numbers that behave like primes.
Exercise: Write a function is_prime_like that takes in an integer n and returns True if n is prime-like and False otherwise. Include a preceding Markdown cell that explains what the function does and how it works, and include code comments that connect to the Markdown explanation for clarification.
Exercise: Write a function get_prime_decomp that takes in an integer n and returns a list containing the prime decomposition of n. Include a preceding Markdown cell that explains what the function does and how it works, and include code comments that connect to the Markdown explanation for clarification.
Finding false primes¶
In order to find false primes for the project, we will want to make use of both the is_prime and is_prime_like functions. In order to find 20 false primes, we will want these two functions to be as efficient as we can manage. The project page discusses using the pow function to help the is_prime_like function run faster than using something like a**n % n.
What about the is_prime function? Can we do anything to make this more efficient?
It would be helpful to have some mechanism for quantifying the efficiency of a function or piece of code.
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 is_primes function. The time module contains tools relating to time, which we can use to time the is_primes 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.
import time
The time module contains many functions pertaining to time. We can use the help function to look at the documentation and see some of the available functions.
#help(time)
For example, the asctime function from the time module gives a string specifying the current time.
time.asctime()
'Wed Sep 16 17:23:29 2026'
Another is the time function from the time module. This function returns the number of seconds (as a float) since the Epoch. We can use this function to time how long it takes for some code to run.
t = time.time()
print(t)
print(t / 60)
print(t / 60 / 60)
print(t / 60 / 60 / 24)
print(t / 60 / 60/ 24/ 365)
1789593809.9754052 29826563.499590088 497109.3916598348 20712.891319159782 56.747647449752826
t0 = time.time()
t1 = time.time()
print(t1 - t0)
0.16558003425598145
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).
For example, if we try to directly call on the asctime function, we will get an error.
asctime()
--------------------------------------------------------------------------- NameError Traceback (most recent call last) Cell In[9], line 1 ----> 1 asctime() NameError: name 'asctime' is not defined
from time import asctime
asctime()
time()
--------------------------------------------------------------------------- TypeError Traceback (most recent call last) Cell In[10], line 1 ----> 1 time() TypeError: 'module' object is not callable. Did you mean: 'time.time(...)'?
from time import time
time()
1789593812.3744867
import time
Exercise: Time how long it takes the is_prime function to test whether $n = 100,000,007$ is prime.
def is_prime(num):
num_is_prime = True
for d in range(2,num):
if (num % d == 0):
num_is_prime = False
break
return num_is_prime
n = 100_000_007
t0 = time.time()
print(is_prime(n))
t1 = time.time()
print('Elapsed time:',t1-t0)
True Elapsed time: 6.164522409439087
Exercise: Time two different versions of the is_prime_like function, one which uses the pow function and one which does not, testing whether $n=10,007$ is prime-like.
Optimizing the is_prime function¶
For the first project, we will need to call upon the is_prime function many times. With that in mind, it will be good to try to make the is_prime function more efficient so that our code can run in a reasonable amount of time.
def old_is_prime(num):
num_is_prime = True
for d in range(2,num):
if (num % d == 0):
num_is_prime = False
break
return num_is_prime
Exercise: Rewrite the is_prime function to take advantage of the $\sqrt{n}$ optimization discussed in class. We can use the sqrt function from the math module to compute square roots.
from math import sqrt
def is_prime(num):
num_is_prime = True
for d in range(2, int(sqrt(num)) + 1):
if (num % d == 0):
num_is_prime = False
break
return num_is_prime
is_prime(101)
True
Exercise: Compare the runtime for the old is_prime function (without optimization) to the newly optimized is_prime function when checking whether $n = 100,000,007$ is prime.
Note: When defining integers, Python will ignore interior underscores. These can be used in place of commas to help with readability.
n = 100_000_007
t0 = time.time()
old_is_prime(n)
t1 = time.time()
print(t1-t0)
7.458502292633057
t0 = time.time()
is_prime(n)
t1 = time.time()
print(t1-t0)
0.0007824897766113281
def is_false_prime(num):
if is_prime_like(num) and not is_prime(num):
return True
else:
return False