Wednesday, September 2nd 2026

Last class, we started working with boolean expressions and if/elif/else blocks. We finished with writing some code that would count, out of the first N positive integers, how many had remainder rem after raising them to the exp-th power and dividing by div.

N = 40
div = 11
rem = 1
exp = 5

powers = []
for num in range(1,N+1):
    powers.append(num**exp)


powers_with_rem = []
for power in powers:
    if (power % div == rem):
        powers_with_rem.append(power)

num_powers_with_rem = len(powers_with_rem)

output_str = '{} of the first {} {}th powers have remainder {} after divison by {}.'
print(output_str.format(num_powers_with_rem, N, exp, rem, div))

19 of the first 40 5th powers have remainder 1 after divison by 11.

Exercise: Use the code above inside a for loop to count how many of the first $1000$ cubes have remainder $0$, then remainder $1$, then remainder $2$, then remainder $3$ after division by $4$.

N = 600
div = 7
exp = 3

powers = []
for num in range(1,N+1):
    powers.append(num**exp)
        
for rem in range(div):
    powers_with_rem = []
    for power in powers:
        if (power % div == rem):
            powers_with_rem.append(power)
    
    num_powers_with_rem = len(powers_with_rem)
    
    output_str = '{} of the first {} {}th powers have remainder {} after divison by {}.'
    print(output_str.format(num_powers_with_rem, N, exp, rem, div))

85 of the first 600 3th powers have remainder 0 after divison by 7.
258 of the first 600 3th powers have remainder 1 after divison by 7.
0 of the first 600 3th powers have remainder 2 after divison by 7.
0 of the first 600 3th powers have remainder 3 after divison by 7.
0 of the first 600 3th powers have remainder 4 after divison by 7.
0 of the first 600 3th powers have remainder 5 after divison by 7.
257 of the first 600 3th powers have remainder 6 after divison by 7.

Prime numbers

Our first project will deal with prime numbers. It will be useful if we can develop some code to decide whether a given integer is prime or not. One strategy for checking whether a given number is prime or not is to look for numbers that evenly divide it. That is, we can test a number $n$ for primality by looking for numbers $d$ such that the remainder from dividing $n$ by $d$ is zero.

33 % 3 == 0

True

N = 40

for d in range(2,N):
    if (N % d == 0):
        print('40 is divisible by',d)

40 is divisible by 2
40 is divisible by 4
40 is divisible by 5
40 is divisible by 8
40 is divisible by 10
40 is divisible by 20

Exercise: Write code that will set a Boolean variable to True if an integer n is prime and will set the Boolean variable to False if not.

N = 43 * 10**7

is_prime = True
for d in range(2,N):
    if (N % d == 0):
        is_prime = False

if is_prime:
    print(N,'is prime.')
else:
    print(N,'is not prime.')

430000000 is not prime.

The break and continue commands

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

for num in range(10):
    print(num)

print('Done')

0
1
2
3
4
5
6
7
8
9
Done

for num in range(10):
    print(num)
    if num == 4:
        break

print('Done')

0
1
2
3
4
Done

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

N = 43 * 10**7

is_prime = True
for d in range(2,N):
    if (N % d == 0):
        is_prime = False
        break

if is_prime:
    print(N,'is prime.')
else:
    print(N,'is not prime.')

430000000 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.

for num in range(10):
    print(num)
print('Done')

0
1
2
3
4
5
6
7
8
9
Done

for num in range(10):
    if (num % 3 == 0):
        continue
    print(num)
print('Done')

1
2
4
5
7
8
Done

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. In this case, a for loop isn't suitable.

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.

for num in range(10):
    print(num)

0
1
2
3
4
5
6
7
8
9

num = 0

while (num < 10):
    print(num)
    num = num + 1

0
1
2
3
4
5
6
7
8
9

num = 0

while (num**2 < 1000):
    print(num**2)
    num = num+1

0
1
4
9
16
25
36
49
64
81
100
121
144
169
196
225
256
289
324
361
400
441
484
529
576
625
676
729
784
841
900
961

We can also use break to terminate a while loop.

num = 0

while True:
    print(num)
    num = num + 1
    if num >= 10:
        break

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

num = 0
while num < 10:
    print(num)
    num += 3

0
3
6
9

num = 1
while num < 100:
    print(num)
    num *= 3

1
3
9
27
81

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

num_cubes = 100

div = 4
rem = 1
exp = 3

powers_with_rem = []
num = 0
while len(powers_with_rem) < num_cubes:
    if (num**exp % div == rem):
        powers_with_rem.append(num**exp)
    num += 1

print(powers_with_rem)

[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.

num_primes = 100
primes = []

num = 2

while (len(primes) < num_primes):
    is_prime = True
    for d in range(2,num):
        if (num % d == 0):
            is_prime = False
            break

    if is_prime:
        primes.append(num)

    num += 1

print(primes)

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541]

Functions in Python

Very often, we want to write code that can be applied to many different inputs. For example, we might want to test many different numbers to check whether they are primes (as in the above). We can accomplish this by writing a Python function. The syntax for defining functions in Python is: def <function name>(<some inputs, separated by commas>): ...do something...

As another reminder: the spacing is part of the code. Lines that are indented are considered part of the function, and once we un-indent back to vertically align with def <function name>(...), we're no longer inside the function.

def f():
    print('Hello world!')

def g(x,y):
    print(x * y)

Notice that when we define a function, the actions included inside are not immediately performed.

Instead, after defining a function we can call upon it to execute the function's code. To call a function, we simply write <function name>(<whatever inputs that are necessary, separated by commas>).

f()

Hello world!

g(3,7)

21

g('Wednesday', 5)

WednesdayWednesdayWednesdayWednesdayWednesday

Exercise: Write a function called is_prime that takes in a variable n and prints whether or not n is prime. Then test your function against the integers from $2$ to $40$.

num = 43

is_prime = True
for d in range(2,num):
    if (num % d == 0):
        is_prime = False
        break

if is_prime:
    print(num, 'is prime.')
else:
    print(num, 'is not prime.')

43 is prime.

The return command

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 object (e.g. a list, a float, an integer, a string, etc) to the caller. This can be done using a return statement. The syntax is: def <function name>(<some inputs, separated by commas>): ...do something... return <some object to be returned>

When calling a function that returns something, we can store the output as a new variable. For example, output = <function name>(<whatever inputs that are necessary>) will store the returned object as the variable output.

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

Note: Whenever a function hits a return statement, it will immediately terminate after returning the corresponding object. That is, none of the code in the function will be run after it hits a return statement.

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

Functions and namespaces in Python

In Python, there are various levels at which variables can be defined. If we define a variable directly within a cell (or within a loop or if block), then that variable is globally available. We say that it is part of the global namespace. Any other piece of code can call upon this variable as needed.

For example, when writing a function, we can make use of this variable within the function. If a function calls upon a variable that has not been defined within that function, it will look outside to see if it has been defined globally, and if so, use the globally defined value.

On the other hand, variables that are defined within a function only exist locally within that function. Consider the following code snippets that illustrate this point.

Notice that, while the function g has internally defined new_variable, that definition does not extend outside of the function. When trying to access new_variable from outside of the function, we get an error.

Similarly, if we redefine a globally defined variable within a function, that new definition only holds within the function.

Notice that, while the function f has internally redefined variable to take on a new value, that has not changed the value of the globally defined variable.

When calling upon functions, they have their own local namespace. That is, they have their own collection of defined variables that is separate from the global namespace. However, as we've seen, these local namespaces can inherit variables from the global namespace if they call upon a name that has not been locally defined.

Exercise: Write a function that takes in an integer n and returns the first n prime numbers.

Exercise: Write a function get_prime_factors that takes in a positive integer n and return a list of all prime numbers that divide n.