I have formed an algorithm and I am not able to optimize it to get the runtime in time. I guess my algorithm shouldn’t take a lot of time. Please suggest what I should I do to get it running in the time limit
def is_prime(k) :
if k == 0 or k == 1 :
return False
for i in range(2, k) :
if k % i == 0 :
return False
return True
def what_number(x, y) :
if x == 0 and y == 0 :
return 0
elif x > 0 and abs(x) > abs(y) :
if y > 0 :
return ((2*x - 1) ** 2) + x + y - 1
else :
return ((2*x - 1) ** 2) + x - abs(y - 1)
elif x < 0 and abs(x) >= abs(y) :
return ((2 * x) ** 2) + abs(x) - y
elif y > 0 and abs(y) >= abs(x) :
return (y * ((4 * y) - 1) - x)
elif y < 0 and abs(y) >= abs(x) :
return ((2 * abs(y)) * ((2 * abs(y)) + 1)) + x - y
t = int(input())
x, y = 0, 0
k = 0
inp = []
for i in range(t) :
coord_string = input()
x = int(coord_string[0 : coord_string.find(' ')])
y = int(coord_string[coord_string.find(' ') + 1 : ])
inp.append([x, y])
for ls in inp :
x = ls[0]
y = ls[1]
e = [x - 1, y + 1]
s = [x + 1, y + 1]
w = [x + 1, y - 1]
n = [x - 1, y - 1]
k = 1
dist = []
while k :
if is_prime(what_number(x, y)) :
dist.append(0)
break
for i in range(0, k + 1) :
if is_prime(what_number(e[0], e[1])) :
(dist.append(abs(x - e[0]) + abs(y - e[1])))
if is_prime(what_number(w[0], w[1])) :
(dist.append(abs(x - w[0]) + abs(y - w[1])))
if is_prime(what_number(n[0], n[1])) :
(dist.append((abs(x - n[0]) + abs(y - n[1]))))
if is_prime(what_number(s[0], s[1])) :
(dist.append(abs(x - s[0]) + abs(y - s[1])))
e[0] += 1
s[1] -= 1
w[0] -= 1
n[1] += 1
if len(dist) > 0 :
break
n, e = e, n
n, s = s, n
n, w = w, n
e = [e[0] - 1, e[1] + 1]
s = [s[0] + 1, s[1] + 1]
w = [w[0] + 1, w[1] - 1]
n = [n[0] - 1, n[1] - 1]
k = k + 2
dist.sort()
print (dist[0])
Also please can someone tell me whether this algo runs for all the values.