一本通信息学奥赛2034

### 关于信息学奥赛编号为2034的题目及解析

#### 题目描述
信息学奥赛编号为2034的题目涉及数论中的素数判定与分解因数问题。具体来说，给定一个正整数 \( n \)，要求编写程序来判断该数是否为素数，并输出其所有的质因子及其指数形式。

对于输入的一个正整数 \( n (2 ≤ n ≤ 1,000,000) \)，如果它是合数，则需进一步求解并打印出它的标准分解式；如果是素数则只需简单返回 "Prime" 表示这是一个素数[^1]。

#### 解析过程
为了实现上述功能，可以采用试除法来进行初步筛选，即从小到大依次尝试去除以小于等于平方根范围内的所有可能的因子。当找到第一个能被n整除的小于\( sqrt(n) \) 的自然数p时，就可以断言p是一个质因子。之后继续对商做同样的操作直到无法再分为止。最后得到的结果就是原数值的标准分解表达方式[^2]。

下面是具体的算法流程：

- 对于任意给定的正整数 `num` ，先检查它是不是偶数且大于2的情况，若是直接给出结果；
- 接着从最小奇数3开始遍历至不大于 \(sqrt(num)\) 的位置，每次增加步长为2（只考虑奇数），一旦发现能够整除就记录下当前这个因子以及对应的次数；
- 如果经过以上步骤后仍然没有找到任何因子说明此数本身就是一个较大的素数；
- 将最终获得的信息按照指定格式整理成字符串输出即可。

#### Python 实现代码

import math

def prime_factorization(num):
    factors = []
    
    # Handle even numbers first
    count = 0
    while num % 2 == 0:
        num //= 2
        count += 1
    
    if count > 0:
        factors.append((2, count))
        
    # Check odd divisors up to square root of number
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        count = 0
        while num % i == 0:
            num //= i
            count += 1
            
        if count > 0:
            factors.append((i, count))

    # If remaining value is greater than two then it must be a prime factor.
    if num > 2:
        factors.append((num, 1))

    return ' '.join(f"{factor}^{exp}" if exp != 1 else str(factor) for factor, exp in factors) or "Prime"

print(prime_factorization(int(input())))