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**