Prime number finder in Python3

Question

The problem

I am working towards improving my Python coding. I am checking that I am doing the best in terms of the Python code, not necessarily the algorithms. Having looked at one of my previous attempts in C++, I learned about Sieves for prime numbers.

I want to know that I am following the proper Python coding "standards" (i.e. PEP8), and there aren't any weird issues I'm overlooking. The run times in comment blocks show the function's run time with my computer, and your results may vary.

The code

"""Prime number generator"""
import math
import argparse
import datetime


def is_odd(number: int):
    """Returns true if the integer passed is an odd number"""
    return number % 2 == 1


def is_prime(number: int):
    """Returns true if the integer passed is a prime number"""
    for _ in range(2, int(math.sqrt(number)) + 1):
        if number % _ == 0:
            return False
    return True
    # Run time: 11.808096
    # Params: minimum=40, maximum=999999


def is_sieved(minimum: int, maximum: int, count: bool):
    """Return list of numbers that are prime"""
    initial_list = range(minimum, maximum)
    list_of_primes = set(initial_list)
    for x in range(2, int(math.sqrt(maximum)) + 1):
        first_loop_of_numbers = True
        for y in range(x, maximum + 1, x):
            if not first_loop_of_numbers:
                list_of_primes.discard(y)
            first_loop_of_numbers = False
    print(f"{list_of_primes=}")
    if count:
        print(f"Primes found: {len(list_of_primes)}")
    # Run time: 02.103035 (min 2 | max 999999)
    # Run time: 25.752799 (min 2 | max 9999999)


def main(minimum: int, maximum: int, count: bool):
    """Main function"""
    if minimum <= 1:
        print("Warning: Minimum set to less than 2. Setting to 2...")
        minimum = 2
    if is_odd(maximum):
        maximum = maximum + 1
        # Maximum must be even for range() to include it
    if minimum >= maximum:
        print("Error! Maximum must be an integer higher than Minimum! Current"
              + f"values: {minimum=} | {maximum=}")
        return 2
    # for number in range(minimum, maximum, 2):
    #     if is_prime(number):
    #         print(f"{number}", end=", ", flush=True)
    is_sieved(minimum, maximum, count)
    print()
    return 0


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="Prime number generator")
    parser.add_argument('--minimum', dest='minimum', type=int, default=2,
                        help='Minimum number to check (default: 2)')
    parser.add_argument('--maximum', dest='maximum', type=int, default=100,
                        help='Minimum number to check (default: 100)')
    parser.add_argument('--count', dest='count', action='store_true',
                        help="Count the number of primes found")
    args = parser.parse_args()
    begin_time = datetime.datetime.now()
    main(args.minimum, args.maximum, args.count)
    end_time = datetime.datetime.now()
    print(f"Execution time: {end_time - begin_time}")

Answer 1

Throw-away variable

The _ variable is used when you need a variable for syntactic correctness, but don’t actually need to ever use the variable. In is_prime, this is not the case; you loop over a range of trial divisors, and then check if the value is divisible by each of those divisors. The variable needs a name!

    for divisor in range(2, int(math.sqrt(number)) + 1):
        if number % divisor == 0:
            return False

Integer square-root

The int(math.sqrt(number)) expression may cause you grief. The calculation is done using floating-point arithmetic. If number is large (over 9,007,199,254,740,992), the conversion to floating-point is not exact and will result in loss of one or more of the least-significant bits. When the square-root is computed on this modified value, it is possible for the square-root to fall on the wrong side of an exact integer, and when converted to an int, the value may end up larger or smaller than the exact mathematical result should be.

This can be trivially avoided by using math.isqrt(number), which by avoiding the floating-point conversion, always computes the correct value. It is also clearer, being four characters shorter to type and eliminating a pair of parenthesis. It should also be faster.

0 and 1 are not prime

The is_prime() function returns True for the numbers 0 and 1, neither of which are considered to be prime numbers.

It is true that your main function enforces a lower limit of 2 on the prime number search range, so it should never be called with values less than 2, but it is valid to write from … import is_prime in other modules where this restriction may not be present. The function should be flagged “not for external use” by prefixing the name with an underscore (_is_prime), or it should behave correctly for all values.

Misleading help

    parser.add_argument('--maximum', dest='maximum', type=int, default=100,
                        help='Minimum number to check (default: 100)')

Is --maximum really setting the minimum number to check?

Efficiency

Setting first_loop_of_numbers to True outside of the for loop, and inside the loop testing it and clearing it, just to do something different on the first iteration of a loop, results in a lot of unnecessary work being done by the processor. It is simpler to “unroll the loop”, doing the “first iteration” explicitly before the loop, and the “remaining iterations” inside the loop with no unnecessary tests required.

In this particular case, your “doing something different on the first iteration” is actually ensuring nothing is done on the first iteration. So really you could just start the loop at the second iteration, by adding the increment to the starting value:

    for x in range(2, int(math.sqrt(maximum)) + 1):
        for y in range(x + x, maximum + 1, x):
            list_of_primes.discard(y)

Timing

Using datetime.datetime.now() for profiling is not the best idea. A lot of additional unnecessary work is being performed to handle timezones. A better choice would be time.perf_counter().

Separate computation and printing

The name of the function is_sieved suggests it returns a True or False result. The """docstring""" describes it as returning a list of numbers. In actuality, neither is correct; it returns None, and prints the prime numbers it found.

The function would be better called sieve_and_print_primes(…). Best would be to perform the sieve in one function, and print the results in a different function.

def sieve(minimum: int, maximum: int) -> set[int]:
    …
    return list_of_primes

def report(list_of_primes: set[int], count: bool) -> None:
    print(f"{list_of_primes=}")
    if count:
        print(f"Primes found: {len(list_of_primes)}")

def main(…):
    …
    primes = sieve(minimum, maximum)
    report(primes, count)
    …

This also gives you the ability to time just the sieve without the I/O (which may involve scrolling output in your shell window) slowing down the program.

def main(…):
    …
    begin_time = time.perf_counter()
    primes = sieve(minimum, maximum)
    end_time = time.perf_counter()
    report(primes, count)
    print(f"Calculation time: {end_time - begin_time}")
    …

Types

list_of_primes is actually a set, not a list. This also means the prime numbers are not returned in ascending order as one may expect.

Range

    if is_odd(maximum):
        maximum = maximum + 1
        # Maximum must be even for range() to include it

I understand what you mean, but this is the wrong. If there was some large even number that was prime, your algorithm wouldn’t find it if it was given as the maximum, because is_odd(maximum) wasn’t true.

Don’t adjust the range based on a condition. Always adjust the range. The clearest way is by adjusting it where it is used:

    initial_list = range(minimum, maximum + 1)

Every Python programmer understands this to mean to include the end point.

Answer 2

Your code is readable, consistant and adheres to all the PEP8 standards I have to follow. I wouldn't worry about any further nit picks.

One preference I have - If I am defining the parameter type, I would also define the return type:

def is_odd(number: int) -> bool: