SolutionEuler/solutions/0037.TruncatablePrimes/euler_37_primeclass.py

"""
The number 3797 has an interesting property.
Being prime itself, it is possible to continuously remove digits from left to right,
and remain prime at each stage: 3797, 797, 97, and 7.
Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.
"""

import math
import random
import time


def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"{func.__name__} taken: {end_time - start_time:.6f} seconds")
        return result

    return wrapper


def miller_rabin_test(n: int, k: int = 10) -> bool:
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    r, s = 0, n - 1
    while s % 2 == 0:
        r += 1
        s //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, s, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True


class PrimeGenerator:
    """质数生成器"""

    _cache = []

    def __init__(self):
        # self._cache = []  # 缓存已生成的质数
        self._generator = self._prime_generator()

    @classmethod
    def is_prime(cls, n: int) -> bool:
        """检查是否为质数（使用缓存优化）"""
        if n < 2:
            return False

        # 检查缓存
        if cls._cache:
            limit = int(math.isqrt(n))
            for p in cls._cache:
                if p > limit:
                    break
                if n % p == 0:
                    return False

        # 使用Miller-Rabin测试
        return miller_rabin_test(n)

    def _prime_generator(self):
        """生成质数的内部生成器"""
        n = 2
        yield n

        n = 3
        while True:
            if self.is_prime(n):
                PrimeGenerator._cache.append(n)
                yield n
            n += 2

    def __iter__(self):
        return self

    def __next__(self) -> int:
        return next(self._generator)

    def __call__(self, start: int = 2):
        """从指定位置开始生成质数"""
        # 重置生成器到指定位置
        self._generator = self._prime_generator_from(start)
        return self

    def _prime_generator_from(self, start: int):
        """从指定位置开始的生成器"""
        if start < 2:
            n = 2
        else:
            n = start if start % 2 else start + 1

        while True:
            if self.is_prime(n):
                yield n
            n += 2

    def primes_up_to(self, limit: int):
        """生成所有不超过limit的质数"""
        if limit < 2:
            return

        yield 2

        n = 3
        while n <= limit:
            if self.is_prime(n):
                yield n
            n += 2

    def nth_prime(self, n: int) -> int:
        """获取第n个质数（从1开始）"""
        if n < 1:
            raise ValueError("n必须大于0")

        # 如果已经在缓存中，直接返回
        if n <= len(PrimeGenerator._cache):
            return PrimeGenerator._cache[n - 1]

        # 否则继续生成直到第n个
        gen = self._prime_generator()
        for _ in range(n):
            result = next(gen)
        return result


def truncate_number(number: int) -> list[int]:
    """生成一个数的所有截断形式"""
    str_num = str(number)
    return [int(str_num[:i]) for i in range(1, len(str_num))] + [
        int(str_num[i:]) for i in range(len(str_num))
    ]


@timer
def main() -> None:
    primes = PrimeGenerator()
    res = []
    n = 0
    while n < 11:
        prime = next(primes)
        if prime < 10:
            continue
        truncate = truncate_number(prime)
        if all(primes.is_prime(trunc) for trunc in truncate):
            res.append(prime)
            print(prime)
            n += 1
    print(f"Sum is : {sum(res)}")


if __name__ == "__main__":
    main()