num = 10 ** 6 #素因数分解したい最大の数def primes(n): is_prime = [True] * (n + 1) is_prime[0] = False is_prime[1] = False for i in range(2, int(n**0.5) + 1): if not is_prime[i]: continue for j in range(i * 2, n + 1, i): is_prime[j] = False…