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 import
s, 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) -> (Optional[Union[bool, int]], Optional[AnyStr]):
if num <= 1:
return 0, "Neither prime nor composite."
if num <= 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.