Help me in solving SPCP5 problem

help
,
1

My issue

how can i solve this using recursion in python
need the test case to which it is returning “runtime limit exceeded”

My code

# cook your dish here

def prime(n):
    if n == (0 or 1):
        return False
    for i in range(2,n//2):
        if n%i == 0:
            return False
    return True
    
def defeat(h,i,c):
    if h < 0:
        return -1
    if h == 0 or prime(h):
        c += 1
        return c
    else:
        return defeat(h-i,i*2,c+1)
        
for _ in range(int(input())):
    h = int(input())
    print(defeat(h, 1, 0))

Problem Link: Monsters Practice Coding Problem - CodeChef

2

Your prime check is very suboptimal (rest seems ok).
There are 1000 testcases with n limited to 10^6, so you have about 20000 calls to prime() maximum. Trial division should be ok, but limit your loop to isqrt(n).
For more demanding problems, you should prepend the testcases with some setup, like (in this case): doing prime sieve (n=10^6) or precomputing primes below 1000 for trial division.

3

Thanks for responding