Kattis prime reduction challenge

Question

I am solving the Prime Reduction challenge on Kattis.

Consider the following process, which we’ll call prime reduction. Given an input x:

1. if x is prime, print x and stop
2. factor x into its prime factors p₁, p₂, …, p_k
3. let x = p₁ + p₂ + ⋯ + p_k
4. go back to step 1

Write a program that implements prime reduction.

Input

Input consists of a sequence of up to 20000 integers, one per line, in the range 2 to 10⁹. The number 4 will not be included in the sequence (try it to see why it’s excluded). Input ends with a line containing only the number 4.

Output

For each integer, print the value produced by prime reduction executed on that input, followed by the number of times the first line of the process executed.

I have already solved it using Java. Now I am trying to solve it in python. My code did well on the sample tests, but on the second test my code fails due to time limit exceeded.

Someone could tell me what I did wrong?

My python code:

import sys
from math import sqrt, floor

def is_prime_number(number):
    if number == 2:
        return True
    if number % 2 == 0:
        return False
    return not any(number % divisor == 0 for divisor in range(3, floor(sqrt(number)) + 1, 2))

def sum_prime_factors(number):
    factors = 0
    while number % 2 == 0:
        factors += 2
        number = floor(number / 2)
    if is_prime_number(number):
        factors += number
        return factors
    for factor in range(3, floor(sqrt(number)) + 1, 2):
        if is_prime_number(factor):
            while number % factor == 0:
                factors += factor
                number = number / factor
            if number == 1:
                return factors 
    factors += number
    return factors

def print_output(x, i):
    if is_prime_number(x):
        print(x, i)
        return
    i = i + 1
    factors = sum_prime_factors(x)
    print_output(factors, i )

[print_output(item, 1) for item in map(int, sys.stdin) if item != 4]

Answer 1

Some ideas:

• is_prime_number doesn't scale well when dealing with bigger primes - the range of odd numbers 3..sqrt(number) is going to get very big. You'd be better off implementing a more sophisticated algorithm such as Eratosthenes' Sieve, where the cost of checking primality of subsequent primes grows slower.
• sum_prime_factors duplicates the implementation of primality checking from is_prime_number.

• [print_output(item, 1) for item in map(int, sys.stdin) if item != 4] is awkward. I would use a main method and any of the common

  if __name__ == '__main__':
      main()
  

  patterns for making the code reusable and testable.

Answer 2

Efficiency

Your is_prime_number() is a very expensive test, and it should not need to exist at all. Rather, the algorithm to factorize the number should just naturally produce only prime factors, never composite factors.

Your sum_prime_factors() is also very inefficient, because it always tries factors up to floor(sqrt(number)) — even after number has been reduced by number = number / factor.

Another relatively minor inefficiency is that you should be using integer division (the // operator) rather than floating-point division (the / operator).

Style

sum_prime_factors() should be broken up, so that it is a generator that yields prime factors. Then, you can call the built-in sum() function on its outputs.

print_output() should be named prime_reduction(), and it should return a pair of numbers rather than printing them. It should also be modified to use a loop rather than calling itself recursively, because recursion is slower and risks overflowing the stack.

The main loop (the last statement of the program) is an abuse of list comprehensions — it should be a loop instead. As a matter of style, you shouldn't use a list comprehension if the resulting list is to be discarded. Furthermore, in this case, a "4" as input is skipped and does not cause the program to terminate. Rather, the program ends due to the EOF rather than the "4".

Suggested solution

from itertools import chain, count
from math import floor, sqrt
import sys

def prime_factors(n):
    limit = floor(sqrt(n))
    for f in chain([2], count(3, 2)):
        while n % f == 0:
            yield f
            n //= f
            limit = floor(sqrt(n))
        if f > limit:
            if n > 1:
                yield n
            break

def prime_reduction(n):
    for i in count(1):
        s = sum(prime_factors(n))
        if s == n:
            return s, i
        n = s

if __name__ == '__main__':
    for n in map(int, sys.stdin):
        if n == 4:
            break
        print(*prime_reduction(n))

Answer 3

As others have stated, is_prime_number is a bit inefficient, as well as being called a lot. You might consider caching its result, since it doesn't change. Try something like:

import functools

@functools.lru_cache(maxsize=None)
def is_prime_number(number):
    ...

And you should see a massive time improvement.

If that's not enough, you're going to have to look into an algorithmic change somewhere. The immediate construct that jumps out at me is that the loop in is_prime_number is very similar to the loop in sum_prime_factors. Figuring out how to combine them is likely to be worth your while.