Python prime number checker function I was bored, and I was watching a sci-fi show where people were starting out during a long systems check asking each other whether numbers were prime or not, sort of passing the time as they do their inspections.

The show is irrelevant, but I wondered if I could build a prime number checker in Python 3 that would be very quick.  I know this has been done before, but I was curious whether I could do it on my own.

Now, this works fine for smaller numbers, and is pretty darn quick, a second or two.  But for large numbers, it takes a really long time.

I'm not a coder by profession, though, so I'm pretty sure this could be improved.  Any speed improvements are welcome.

Required imports, and the 'test' function which takes input of a number and spits out the results is below,

Currently, the results spit out a tuple, the first value either being Boolean or the number '0' (because the number '1' is a unique case that is not prime but you can't just say 'False' for), and a short string description.

from typing import AnyStr, Optional, Union

def is_prime(num: int) -&gt; (Optional[Union[bool, int]], Optional[AnyStr]):
    if num &lt;= 1:
        return 0, "Neither prime nor composite."

    if num &lt;= 3:
        return True, "Prime"

    for i in range(2, num):
        if (num % i) == 0:
            return False, "Not Prime"

    return True, "Prime"

if __name__ == "__main__":
    n = int(input("Value: "))
    print(is_prime(n))


I'm curious how I can improve the performance of this code for larger numbers so that it's a fairly fast function, rather than taking a very long time to iterate over values.  I know that the iterations in the for loop are taking the hugest amount of time, but I'm not a mathematician so I'm not sure the 'best' approach for speeding up this.  Don't yell at me too harshly, this was more a quick 'mind test' to see if I could come up with something that worked.
Disclaimer: I can read Python, but I'm not a Python developer.

First of all, your code follows PEP8, which is a plus (although a second empty line before is_prime is necessary). And it's great that you try static type hints.

However, there are two things amiss here. First of all, Optional isn't honest at that point. We always return a value. And we always return a str, not AnyStr. We should therefore change the type hints accordingly:

from typing import Union


def is_prime(num: int) -&gt; (Union[bool, int], str):


If there was a path where we could accidentally return None, None or None, b"12343", a static checker should warn us. So no Optional or AnyStr.

Since the types are now out of a way, let's have a look at documentation before we head to algorithms. A docstring is a nice addition:

def is_prime(num: int) -&gt; (Union[bool, int], str):
    """Checks whether the given number is prime."""

    if num &lt;= 1:
    ...


You can probably come up with a more detailed one so that the code itself contains the meaning of True, False and 0.

Now to the algorithm. Your algorithm has \$\mathcal O(n)\$ worst time complexity. However, for any pair \$x\$,\$y\$, such that \$x &lt; y\$ and \$ x y = n \$ we must have \$x \le \sqrt{n}\$. Therefore, we can stop at math.ceil(sqrt(n)), not n. This yields \$\mathcal O(\sqrt{n})\$ worst time complexity.

For very large numbers this will still be too slow. There are other algorithms for that, which are out of scope for a small review.