# Python 常用算法模板

> [!note]
> 本文收录原 C 语言目录中的 Python 片段，并按可复用模板重新整理。相关解释见 [[计算机系/Python/Python题目知识点梳理.md]]。

## 1. 枚举整数的因数对

只需枚举到 $\sqrt n$。如果 `factor` 是因数，则 `n // factor` 是与之配对的另一个因数。

```python
from math import isqrt


def factor_pairs(n: int) -> list[tuple[int, int]]:
    if n <= 0:
        raise ValueError("n must be a positive integer")

    pairs = []
    for factor in range(1, isqrt(n) + 1):
        if n % factor == 0:
            pairs.append((factor, n // factor))
    return pairs


number = int(input("请输入正整数："))
for left, right in factor_pairs(number):
    print(f"{left} * {right} = {number}")
```

## 2. 生成等差数列并求和

```python
def arithmetic_sequence(first: int, difference: int, count: int) -> list[int]:
    if count < 0:
        raise ValueError("count cannot be negative")
    return [first + difference * i for i in range(count)]


def arithmetic_sum(first: int, difference: int, count: int) -> int:
    if count < 0:
        raise ValueError("count cannot be negative")
    return count * (2 * first + (count - 1) * difference) // 2


first = int(input("首项："))
difference = int(input("公差："))
count = int(input("项数："))

print(arithmetic_sequence(first, difference, count))
print(arithmetic_sum(first, difference, count))
```

## 3. 判断质数

```python
from math import isqrt


def is_prime(number: int) -> bool:
    if number < 2:
        return False
    if number == 2:
        return True
    if number % 2 == 0:
        return False

    for divisor in range(3, isqrt(number) + 1, 2):
        if number % divisor == 0:
            return False
    return True
```

## 4. 筛选指定范围内的质数

```python
upper = int(input("请输入上限："))
primes = [number for number in range(2, upper + 1) if is_prime(number)]
print(primes)
```

此段依赖上一节定义的 `is_prime`。如果需要生成大量质数，可改用筛法：

```python
def sieve(upper: int) -> list[int]:
    if upper < 2:
        return []

    is_prime_table = [True] * (upper + 1)
    is_prime_table[0] = is_prime_table[1] = False

    for number in range(2, int(upper**0.5) + 1):
        if is_prime_table[number]:
            start = number * number
            is_prime_table[start : upper + 1 : number] = [False] * (
                (upper - start) // number + 1
            )

    return [number for number, prime in enumerate(is_prime_table) if prime]
```

## 5. 判断回文数

```python
def is_palindrome_number(number: int) -> bool:
    if number < 0:
        return False
    text = str(number)
    return text == text[::-1]
```

若题目判断的是普通字符串，可写成：

```python
def is_palindrome(text: str) -> bool:
    return text == text[::-1]
```

## 6. 简单自测

```python
assert factor_pairs(12) == [(1, 12), (2, 6), (3, 4)]
assert arithmetic_sequence(2, 3, 4) == [2, 5, 8, 11]
assert arithmetic_sum(2, 3, 4) == 26
assert is_prime(2)
assert is_prime(97)
assert not is_prime(1)
assert not is_prime(100)
assert is_palindrome_number(12321)
assert not is_palindrome_number(-121)
```

`assert` 适合示例和开发阶段的快速检查，但不应替代正式的输入校验或完整测试框架。