华为 OD 机测试 - RSA 加密算法（Python/JS/C/C++ 2024 E 卷 100 分） - V.Python 算法源代码

import math
import sys

def is_prime(a):
    """
    判断一个数是否为素数
    :param a: 要判断的数
    :return: 如果是素数返回True，否则返回False
    """
    if a < 2:
        return False
    sqrt_a = int(math.floor(math.sqrt(a)))
    for i in range(2, sqrt_a + 1):
        if a % i == 0:
            return False
    return True

def main():
    # 读取输入的num
    input_line = sys.stdin.readline().strip()
    if not input_line:
        print("-1 -1")
        return
    num = int(input_line)
    
    # 计算num的平方根n，取整数部分作为循环的终止条件
    n = int(math.floor(math.sqrt(num)))
    # 初始化结果为-1 -1
    result = "-1 -1"
    
    # 遍历从2到n，寻找因子
    for i in range(2, n + 1):
        # 如果num能被i整除，说明i是num的一个因子
        if num % i == 0:
            other_factor = num // i
            # 检查i和num/i是否都是素数
            if is_prime(i) and is_prime(other_factor):
                # 确保输出顺序为从小到大
                if i < other_factor:
                    result = f"{i} {other_factor}"
                else:
                    result = f"{other_factor} {i}"
                # 找到一对因子后，立即终止循环
                break
    
    # 输出结果
    print(result)

if __name__ == "__main__":
    main()