Är det ett primtal

Dynamic Programming

A function evaluating if input integer is prime (in Python script):

def prime(input):
    for n in range(2, input):
        if input%n == 0:
            return False
    return True
   
tal = int(input("ange ett tal"))
if (prime(tal) == True):
  print(tal, "är ett primtal")
else:
	print(tal, "är inte ett primtal")

Essentially, this evaluates whether integer x can be divisible by any number less than it (n = [2, 3, 4, ... , x-2, x-1]). However, there are two redundancies in this method:

1. If input is not divisible by 2, it will not be divisible to any other even number (4, 6, 8, ...).

2. It is not needed to evaluate integers above the square root of the input number. To elaborate, here is an example:

Evaluate if 127 is prime:
127 divisible by 2? No.
127 divisible by 3? No.
127 divisible by 5? No.
127 divisible by 7? No.
127 divisible by 9? No.
127 divisible by 11? No.
Therefore 127 is prime.

We do not need to evaluate if 127 is divisible by 13, because 127^1/2 is around 11.27, which is smaller than 13. If 127 was divisible by 13, then 127/13 would be less than 13 itself and therefore must give an integer already tested. As another example, 143 will be checked if it is prime. Here it will be shown that 13 is not needed to be evaluated once again (143^1/2 ≈ 11.96).

143 divisible by 3? No.
143 divisible by 5? No.
143 divisible by 7? No.
143 divisible by 9? No.
143 divisible by 11? Yes → 143/11 = 13
(143 divisible by 13 not evaluated)
Therefore, 143 is not prime

Hence, our original prime function can be improved using these two suggestions, and now runs at a greater speed! For example, when evaluating if 10001 is prime, the function went through 10000 different numbers. But with these improvements, it only has to go through 50!

from math import ceil
def prime(input):
    for n in [2] + range(3, int(ceil(input**0.5)), 2):
        if input%n == 0:
            return False
    return True

Now, this only tests odd numbers (≥3) and ≤ the square root of the input (hence the ceil function, which can be replaced with a simple "+1").

So here is the lesson to learn from this: the gun is only as accurate as you are.