Ytdyklly

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]

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.

  
  

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))