Implement:
primes_up_to(n): all primes ≤ n with the Sieve of Eratosthenes (start crossing out at p², and stop when p² > n)smallest_prime_factors(n): a list spf of length n + 1 where spf[k] is the smallest prime dividing k (with spf[0] = 0 and spf[1] = 1)factorize(k, spf): the prime factorisation of k as a dict {prime: exponent}, using the table to divide out one factor at a time in O(log k)count_divisors(k, spf): the number of divisors, which is the product of (exponent + 1)