-1
""""
A function that takes a positive integer n as input and prints its prime factorization to 
the screen. 
Gather the factors together into a single string, so that the results of a call like
(60) would be to print the string “60 = 2 x 2 x 3 x 5” to the screen.
Looking for a way to build prime_factorization such that every factor you find will be prime 
automatically.
"""
def prime_factorization(n):
    results = 0
    for i in range(1, n + 1):
        if (n % i) == 0:
            prime = True
            for x in range(2, i):
                if (i % x) == 0:
                    prime = False
            if prime:
                results = results + i
            return results

prime_factorization(60)

Above is my attempt at the problem. I tried to find the factors first and then determine if they are prime. I'm extremely stuck on this and would appreciate any help or suggestions!

Jonathon Reinhart
  • 132,704
  • 33
  • 254
  • 328
Stiff
  • 47
  • 7
  • I'm not looking to use built-in Python algorithms. I'm trying to make my own function that will print a string. – Stiff Feb 11 '21 at 02:26
  • Welcome to Stack Overflow. Please edit your question to clarify: what part of your algorithm isn't working and what question are you hoping to get answered: why your particular code doesn't work, or how to compute the prime factorization in general. See also https://stackoverflow.com/help/how-to-ask. – Julian Feb 11 '21 at 19:49

1 Answers1

1

Try writing this algorithm. No testing for primes needed, but not efficient for numbers with very large prime factors.

  1. Let f = 2
  2. Compute quotient and remainder of f into n.
  3. if no remainder, save f and let n = quotient
  4. if remainder, increment f
  5. Repeat 2-4 until n == 1.
  6. return saved factors.

It took ~2 seconds to compute the prime factors 1-10,000, but ~5.5 seconds to do the next 10,001 to 20,000. It gets worse from there, but then you look for optimizations.

Mark Tolonen
  • 166,664
  • 26
  • 169
  • 251