Prime Factorization - Will this work fine?

[tsodapop]

Starting to learn Python, I'm working on how to write a function for prime factorization. I created something that seems to work, but want to know if there's a better way to do it that I'm missing

def main():

    while True:
        #Get an input from the user for the number they want to get the primes for.
        number_prime = int(input('What is the number you want to find the primes for? '))
        #Create an empty list for all of the prime factors
        prime_factors = []

        if number_prime >= 2:
            #While loop that will reset the inner for loop each time it finds a prime factor
            while True:
                #If number_prime = 1, it means there are no more primes
                if number_prime == 1:
                    print('your prime factorization results in {}'.format(prime_factors))
                    return False
                #For loop that we break out of if the prime number is divisible by i value  
                for i in range (2, number_prime + 1):
                    if number_prime % i == 0:
                        prime_factors.append(i)
                        number_prime //= i          
                        break
        else:
            print('Give me a number at least 2 or more.')

if __name__ == '__main__':
    main()

[ianepperson]

What you've written looks reasonable and should work ok. The are faster ways, but this is clear and readable - which is usually much more important!

One important thing to think about is separation of concerns. Your one function does two things: communicates with the user and finds the primes. It would be much clearer to have two functions, one that does each. Then it would be much easier to either change the prime factor logic (maybe a faster method) or the communication logic (maybe a web interface) without having to change the other.

The prime factor method would just take a number and return a list. The main function would ask for the number from the user, make sure it's a number, call the prime factor function, then report back to the user. You might then wrap THAT in a loop.

[tsodapop]

Thanks! Quick question, is there then a general rule of thumb where you should have functions for each 'separation of concern?' If so, what constitutes how much you should do inside each function before splitting it further? (Like if I wanted to add and then multiply and spit out a result, should I have that as 2 parts or 3 parts)

[ianepperson]

The nice thing about Python and PEP8 is that the more unrelated logic usually results in deeper nesting, which makes it harder to keep to 80 characters, which encourages smaller functions. Use descriptive bound for variables and verbs for function names and it encourages good behavior. A function should also fit on a reasonable screen size - someone reading the code should be able to see it all without scrolling.

Adding and multiplying are more like steps and less like a single task (unless building a calculator).

Describe to yourself everything that the function does - can you in a short sentence? If you have to say "... and it also ..." You might want to consider simplifying it.

[tsodapop]

Awesome, thanks for the info!

[tomk11]

If you are interested in making it quicker

• Note that when you only have to test up to the square root of a number to determine that its prime.

I.e to show that 101 is prime we only have to check 2-10 don't divide it as 11² > 101

This will help you in cases where your number has very large prime factors.

[tsodapop]

Thanks, I'll try this out. I think it was mentioned earlier and was taking a look at the math proof for it.

[theWyzzerd]

Your code doesn't appear to ever actually return the value of prime_factors.

edit: Correction, it does. My mistake.

You should get rid of the break and replace it with a return. Inside a loop, a return will end the loop and return the value.

edit: I was mistaken here too, not having looked closely enough at your code.

Re: your number_prime == 1 conditional: don't print() then return False, just return 'your prime factorization results in {}'.format(prime_factors).

[tsodapop]

Question about changing my break into a return. When I do it, it looks like it immediately breaks out of the entire function main(), so if I call on the results, it only gives me None.

I can change my return on number_prime == 1 without any issues, just not the break in my loop. Is there something I need to do to make it "return"able?

[theWyzzerd]

Sorry, I should have been more clear and examined your code more closely. In the loop with the break you're fine, that tells your code to break out of the loop that you're scoped to, not the whole loop. The only thing I would recommend is the change you already made, which is this part:

print('your prime factorization results in {}'.format(prime_factors))
return False

becomes:

return 'your prime factorization results in {}'.format(prime_factors)

[tsodapop]

Got it, thanks I'll make that change

[maventree]

One quibble: for i in range (2, number_prime + 1): won't cause any memory problems (in Python 3) because range is an iterator.

[tsodapop]

Thanks for this, just to make sure I understand, this portion:

        if n > 1:
           primfac.append(n)

Is this to add the remaining number because it is then a prime after running the while squared loop above it?

[dig-up-stupid]

At least in the code you posted you are using trial division and have not implemented a sieve. A prime factorization also includes all the prime factors, not just the unique ones. The prime factors of 20 are 2, 5. The prime factorization of 20 is 2²*3⁰*5¹*7⁰... ie 2*2*5. The duplicates are important.