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 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.
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]