I am tutoring students in Java II this semester and one of the programming assignments is to determine if a number is **prime number**, and if it is not a prime number, to determine all the **factors** of the given number. A prime number is any number, N, that only has factors of 1 and N. For example, 11 is a prime number, because it only has factors of 1 and 11. The number 6 is not a prime number, because it has factors of 1, 2, 3, and 6.

One way to determine if a number, N, is a prime number is by using **trial division**. Trial division divides N by every number between 2 and the square root of N. If any of those numbers is a factor (divides evenly into N), N is not a prime number.

Although this was a Java II assignment, let's code it in Python.

## Find Factors of a Number in Python

One way to solve this problem is to create a function, called `get_factors`

, that uses trial division to obtain the factors of a number. If this function only returns 2 factors, 1 and N, the number is a **prime number**. If the function returns more than 2 factors, the number is a **composite number**.

We know there will be at least 2 factors for every N, 1 and N, so we will add them to a Python `set`

that keeps track of the factors. Let's then loop through every integer between 2 and the square root of N to see if it is a factor. If it is, add the integer and it's counterpart to the set. Return the factors as a sorted `list`

to the calling function.

def get_factors(number: int) -> list: """ Return the factors of a number. :param number: int, positive integer > 1. :return: lst, a sorted list of the factors. >>> get_factors(2) [1, 2] >>> get_factors(3) [1, 3] >>> get_factors(4) [1, 2, 4] >>> get_factors(100) [1, 2, 4, 5, 10, 20, 25, 50, 100] """ if number < 2 or not type(number) == int: raise ValueError(f'{number} is invalid. Must be a positive integer > 1.') factors = {1, number} max_value = int(math.sqrt(number)) for i in range(2, max_value + 1): if number % i == 0: factors.add(i) factors.add(number // i) return sorted(list(factors))

## Is the Number a Prime Number Using Python

Once we have a function that calculates and returns a list of the factors of a given number in Python, we can check the length of the list to determine if the number is a prime number. If the quantity of factors is 2, the number is a prime number. If the quantity of factors is more than 2, the number is a composite number.

Here is a Python function that asks the user for a number and calculates whether the number is a prime number in Python. If it is not a prime number, it provides a list of the number's factors.

def main(): num = int(input('Enter a positive integer greater than 1: ')) if num < 2: raise ValueError(f'{num} is invalid. Must be a positive integer > 1.') num_factors = get_factors(num) if len(num_factors) == 2: print(f'{num} is a prime number.') else: print(f'{num} is not a prime number with factors {num_factors}.') if __name__ == '__main__': main()

I called the Python script `main.py`

. You can run the Python application from the command prompt.

$ python main.py Enter a positive integer greater than 1: 100 100 is not a prime number with factors [1, 2, 4, 5, 10, 20, 25, 50, 100].

## Doctests for get_factors Python Function

There are a few **doctests** for the `get_factors`

Python function. You can run them from the command prompt.

$ python -m doctest main.py -v Trying: get_factors(2) Expecting: [1, 2] ok Trying: get_factors(3) Expecting: [1, 3] ok Trying: get_factors(4) Expecting: [1, 2, 4] ok Trying: get_factors(100) Expecting: [1, 2, 4, 5, 10, 20, 25, 50, 100] ok

## Conclusion

Determing if a number is a prime number is a cool programming challenge and technical interview question. It's easy enough to solve using trial division, but there are other ways to solve this problem, too.

### Posted by David Hayden

David Hayden is a freelance web developer. In his spare time he tutors students on a wide variety of computer science topics and programming languages. You can find him on twitter as @koderdojo.