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.