exercise-12-3-6.py

from math import sqrt, ceil
from functools import reduce


def is_prime(n: int) -> bool:
    """
    O(sqrt(n))
    """
    return all([n % i != 0 for i in range(2, ceil(sqrt(n)) + 1)])


def product(n: list[int]) -> int:
    """
    O(n)
    """
    return reduce(lambda a, b: a * b, n)


def all_prime(n: list[int]) -> bool:
    return all([is_prime(x) for x in n])


if __name__ == "__main__":
    """
    Primer Integer Factoring Problem --

    We can verify the prime factors of a number in two distinct steps:

    1) Check that all factors are indeed prime
    2) Check the product of the factors to ensure equivalence to pre-factored number

    Since both 1) and 2) are achieved in polynomial time, the
    Integer Factoring Problem is in the class NP.

    *Note: we only need to prove that the verifiability of solutions is polynomial,
    not the solvability.*
    """
    factors = [
        1,
        3,
        5,
        5,
        7,
        11,
    ]  # obtained by running <insert_magic_factoring_algo_here>
    assert all_prime(factors) and product(factors) == 5775
    print("✅")