Problem: Find the minimum prime number greater than or equal to X.

Submission attempts (in order):

def is_prime_miller_rabin(n: int) -> bool:
    """Miller–Rabin primality test in O(k log^3 n).
    https://twitter.com/kiri8128/status/1241033090773860353
    https://www.wikiwand.com/en/Miller%E2%80%93Rabinprimalitytest
    """
    # cut out small primes and 87% of composite numbers.
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}:
        return True
    elif (
        n % 2 == 0
        or n % 3 == 0
        or n % 5 == 0
        or n % 7 == 0
        or n % 11 == 0
        or n % 13 == 0
        or n % 17 == 0
        or n % 19 == 0
        or n % 23 == 0
        or n % 29 == 0
        or n % 31 == 0
        or n % 37 == 0
        or n % 41 == 0
        or n % 43 == 0
        or n % 47 == 0
        or n % 53 == 0
        or n % 59 == 0
        or n % 61 == 0
        or n % 67 == 0
    ):
        return False

    # find the most suitable witnesses for n
    if n < 2047:
        witnesses = [2]
    elif n < 1373653:
        witnesses = [2, 3]
    elif n < 9080191:
        witnesses = [31, 73]
    elif n < 25326001:
        witnesses = [2, 3, 5]
    elif n < 3215031751:
        witnesses = [2, 3, 5, 7]
    elif n < 4759123141:
        witnesses = [2, 7, 61]
    elif n < 1122004669633:
        witnesses = [2, 13, 23, 1662803]
    elif n < 2152302898747:
        witnesses = [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        witnesses = [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    else:  
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True


def main():
    N = int(input())
    if N != 2 and N % 2 == 0:
        N += 1
    while not is_prime_miller_rabin(N):
        N += 2
    print(N)


if __name__ == "main":
    main()



def is_prime(n: int) -> bool:
    """
    Evaluate whether a number is prime or not.

    Args:
        n: a number to evaluate

    Returns: whether n is prime or not
    """
    if n == 2:
        return True
    if n == 1 or n % 2 == 0:
        return False
    for i in range(3, int(n ** 0.5) + 1, 2):
        if n % i == 0:
            return False
    return True


def main():
    N = int(input())
    while not is_prime(N):
        N += 2
    print(N)


if __name__ == "__main__":
    main()



def is_prime_miller_rabin(n: int) -> bool:
    """Miller–Rabin primality test in O(k log^3 n).
    https://twitter.com/kiri8128/status/1241033090773860353
    https://www.wikiwand.com/en/Miller%E2%80%93Rabinprimalitytest
    """
    # cut out small primes and 87% of composite numbers.
    if n < 2:
        return False
    elif n in {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}:
        return True
    elif (
        n % 2 == 0
        or n % 3 == 0
        or n % 5 == 0
        or n % 7 == 0
        or n % 11 == 0
        or n % 13 == 0
        or n % 17 == 0
        or n % 19 == 0
        or n % 23 == 0
        or n % 29 == 0
        or n % 31 == 0
        or n % 37 == 0
        or n % 41 == 0
        or n % 43 == 0
        or n % 47 == 0
        or n % 53 == 0
        or n % 59 == 0
        or n % 61 == 0
        or n % 67 == 0
    ):
        return False

    # find the most suitable witnesses for n
    if n < 2047:
        witnesses = [2]
    elif n < 1373653:
        witnesses = [2, 3]
    elif n < 9080191:
        witnesses = [31, 73]
    elif n < 25326001:
        witnesses = [2, 3, 5]
    elif n < 3215031751:
        witnesses = [2, 3, 5, 7]
    elif n < 4759123141:
        witnesses = [2, 7, 61]
    elif n < 1122004669633:
        witnesses = [2, 13, 23, 1662803]
    elif n < 2152302898747:
        witnesses = [2, 3, 5, 7, 11]
    elif n < 3474749660383:
        witnesses = [2, 3, 5, 7, 11, 13]
    elif n < 341550071728321:
        witnesses = [2, 3, 5, 7, 11, 13, 17]
    elif n < 3825123056546413051:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23]
    elif n < 318665857834031151167461:
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
    else:  
        witnesses = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

    d = n - 1
    d = d // (d & -d)

    for a in witnesses:
        y = pow(a, d, n)
        if y == 1:
            continue
        t = d
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1:
                return False
            t <<= 1
    return True


def main():
    N = int(input())
    if N != 2 and N % 2 == 0:
        N += 1
    while not is_prime_miller_rabin(N):
        N += 2
    print(N)


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Time Limit Exceeded

Accepted