Lab: Prime Decomposition

In this lab, you will write a program that finds the prime decomposition of numbers.

Instructions

You may work either individually or with a partner.

Step 1: Manual Decomposition

First, find the prime decomposition of several numbers using a pencil, paper, and simple calculator.

Factoring by hand will help you develop the algorithm for your Python program.

Step 2: Python Program

You should develop a Python program to find the prime decomposition of a number. Name your program decomposition.py. The program should accept one argument, an integer. The program should print the prime factorization of that number, with factors separated by line breaks. For example:

> python decomposition.py 10
2
5
> python decomposition.py 24
2
2
2
3
> python decomposition.py 3
3

Note: The factors do not need to appear in a particular order.

Hint: You should run your program from the terminal. You can access command line arguments using the sys.argv list.

Optional: Factoring RSA Numbers

Internet security relies on the difficulty of factoring certain large numbers. Your program should factor small numbers easily, but your program will run for a long time if you try to factor RSA numbers. RSA numbers are products of two large prime numbers.

Use the Big Primes website to retrieve RSA numbers of increasing size. See how the runtime of your program changes as you increase the number of bits in the input number.

Further reading:

Submit

Upload decomposition.py to Gradescope.

If you worked with a partner, add them to your submission.

Learning Goals