Python prime number checker function
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.