Kattis prime reduction challenge I am solving the Prime Reduction challenge on Kattis.


  Consider the following process, which we’ll call prime reduction. Given an input x:
  
  
  if x is prime, print x and stop
  factor x into its prime factors p1, p2, …, pk
  let x = p1 + p2 + ⋯ + pk
  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 109. 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]
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.