Amazon HackOn OA | May 2025 | Set - 2

Question

Answer 1

def isPrime(n):

    if n < 2:

        return False

    if n == 2:

        return True

    if n % 2 == 0:

        return False

    i = 3

    while i * i <= n:

        if n % i == 0:

            return False

        i += 2

    return True

def minimumInterest(M):

    currloan = M

    interest = 0

    while currloan >= 2:

        p = currloan

        # make p odd if needed (except 2)

        if p > 2 and p % 2 == 0:

            p -= 1

        # find largest prime <= currloan

        while p >= 2:

            if isPrime(p):

                break

            p -= 2

        currloan -= p

        interest += 1

    return interest

# Input / Output

M = int(input().strip())

print(minimumInterest(M))