Assignment 10: Prime factors

Learning objectives

Working with global "constants"

Implementing a given algorithm

Overview

For this assignment, you shall write a Python script that asks the user for a positive integer between 1 and 1,000. The script shall then print out a list of the prime numbers which are factors of the input value.

Minimal Assignment

For the minimal assignment, the list will simply be a partial list of prime factors.

For this exercise, we will limit our examination to the first 11 prime numbers:

2 3 5 7 11 13 17 19 23 29 31

These first eleven prime numbers shall be stored in a global tuple. [fodder: Why a tuple and not a list? There are multiple parts to this answer. So, if you think of something to say here, please say it, even if someone else has "answered" the question with a different answer.]

Write a function that will accept an integer as a parameter. The function will print out the (partial) list prime factors of the input number. Use an appropriate looping statement to process through all eleven prime numbers. Print out each value which is a factor of the input (parameter) value.

Hint: The remainder operation will be helpful.

In the main function, ask the user for an integer value between 1 and 1,000, inclusive. Convert the input value to int. (You can assume that the user will type in an acceptable value, at this point.) Pass this int value as the argument when you call your function to print out a partial list of prime factors.

Include simple input validation in your function to make sure that the user's input is acceptable, that is, between 1 and 1,000, inclusive. If the user input value is ok, call your function to print out the partial list of prime factors. If it is not, print out an error message instead and end the program.

Here is a sample run. The user input is shown in blue bold text.

Enter a positive integer between 1 and 1,000: 12 2 is a factor of 12. 3 is a factor of 12.

Notice that the output is not a prime factorization of the input value. That would be 2 2 3.

Also notice that the minimal implementation does not get all of the factors of the input number either.

Enter a positive integer between 1 and 1,000: 82 2 is a factor of 82.

The correct solution would also list the prime number, 41. Both of these shortcomings are addressed in the Standard assignment.

Testing your code

Update the main method to test your code. Before asking the user for a numeric value and calling your function, call your function with some "known" int values. This way you can check to make sure that the function is working correctly.

For testing purposes, "hard code" some calls in the main function to your factors function. That way you have some repeated input values that you can use to check that the factors function is working the way you expect.

def main(): # hard-coded test cases factors(12) factors(60) # code to prompt the user for input # perform input validation # call the factors function

You have two tasks for your function in the minimal assignment. They are the function that prints out the primes and input validation code. You should test them both.

All together, there should be 8 test cases. Include the test cases, with the expected results, in the report for the assignment. Only two of the test cases shall test input validation.

The report for the test cases can be very simple. Here is an example for the minimal version.

Test cases: 12: 2 3 82: 2

Standard Assignment

For the standard assignment, you will update the factors function so that it prints out the prime factorization of a positive integer between 1 and 1,000 that is the parameter. Notice, input validation is performed before running the code that calculates the factors.

Here is a sample run. The user input is shown in blue bold text.

Enter a integer between 1 and 1,000: 12 The factors of 12: 2 2 3

Notice that the output format has been updated so that all of the factor information appears on one line.

The Algorithm

The algorithm that you will implement will repeatedly check for multiples of the given primes.

Here's the basic algorithm:

Store the input (parameter) value.

Work through the list of primes in order. We'll work with only one prime at a time. This will be called "current prime".

As long as the current prime evenly divides the input value,

Output the current prime.

Set the input value to its quotient when divided by current prime.

When current prime no longer evenly divides the input value, go to the next prime number in the list.

Repeat until value is 1.

If you reach the end of the list of primes and the input value does not equal one, then that remaining input value is prime. Output that value.

Let's look at a couple of concrete examples:

Enter a integer between 1 and 1,000: 264 The factors of 264: 2 2 2 3 11

Here is the algorithm applied to 264:

We start by prompting the user for an input value. In this example, they enter 264.

We can start the output with " The factors of 264:".

Take the value 264 and divide by the current prime number, 2, the first one. It goes in evenly so 2 is factor. We output the factor 2 and update the value to be the quotient, 132.

Take the value 132 and divide by the current prime, 2. It goes in evenly. Output 2 and update value to the the quotient, 66.

Take the value 66 and divide by the current prime, 2. It goes in evenly. Output 2 and update value to 33.

Take the value 33 and divide by the current prime, 2. It doesn't go in evenly. Go on to the next prime.

Take the value 33 and divide by the current prime, 3. It goes in evenly. Output 3 and update value to 11.

Take the value 11 and divide by the current prime, 3. It doesn't go in evenly. Go on to the next prime.

Take the value 11 and divide by the current prime, 5. It doesn't go in evenly. Go on to the next prime.

Take the value 11 and divide by the current prime, 7. It doesn't go in evenly. Go on to the next prime.

Take the value 11 and divide by the current prime, 11. It goes in evenly. Output 11 and update value to 1.

Since value is 1, end the processing.

Enter a integer between 1 and 1,000: 246 The factors of 246: 2 3 41

Here is the algorithm applied to 246:

We start by prompting the user for an input value. In this example, they enter 246.

We can start the output with " The factors of 246:".

Take the value 246 and divide by the current prime, 2. It goes in evenly. Output 2 and update value to 123.

Take the value 123 and divide by the current prime, 2. It doesn't go in evenly. Go on to the next prime.

Take the value 123 and divide by the current prime, 3. It goes in evenly. Output 3 and update value to 41.

Take the value 41 and divide by the current prime, 3. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 5. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 7. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 11. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 13. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 17. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 19. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 23. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 29. It doesn't go in evenly. Go on to the next prime.

Take the value 41 and divide by the current prime, 31. It doesn't go in evenly. Go on to the next prime.

There are no more primes in the list. Output value 41, since it is not equal to 1. End the processing.

Make sure that you end the output line with a newline character. For aesthetic reasons, you could add a second newline character after printing the factors.

Now that the function is printing a prime factoring of the input value, make sure you update the expected value for your test cases.

Test cases

The test cases shall be included as part of the homework submission. These test cases are simply the input values that you hard-coded into main and expected results for those input values. Submit your test cases (input values and expected results) in the written report.

Here is an example of submitting the test cases in the written report:

For the minimal version:

12: 2 3 60: 2 3 5 82: 2

For the standard and challenge versions, the same input values would have different expected results:

12: 2 2 3 60: 2 2 3 5 82: 2 41

You shall submit at least 8 different test cases. They may include these 3. You will need to create 5 more. These should be different than your classmates. (So, don't pick obvious values for your 5 test cases.)