A more pythonish code

[John Posner]

On 2/25/2010 7:23 AM, prasad_chand wrote:
> Hi,
>
> I use python to do simple math problems as a hobby.
>
> I have made a program that finds the number of divisors(factors) of a
> given number. I am hoping to improve my language skills, specifically
> I would like to re-write the function "prime_factors" more gracefully.
> While the program works right, I am hoping that I could get some input
> on how to write better python code. I have attached the code below.
>
>
> def prime_factors(n):
>      """
>      Reduce a number to its prime factors. e.g. 48 is 2^4,3^1 (add (4+1)
> (1+1) = 10)
>
>      Updates a global dictionary(my_dict) with prime numbers and number
> of occurances. In the case of 48 {2:4,3:1}
>
>      """
>      tmp_n = n

A name meaning "temporary value of n" doesn't suggest how it's being 
used in the algorithm. In my implementation (see below), I used the name 
"last_result", which is (a little bit) better.
>
>      while True:
>
>          if tmp_n == 1:
>              break
>
>          tmp_check = tmp_n
>
>          for x in range(2,int(ceil(sqrt(tmp_n)) + 1)):
>              if tmp_n % x == 0:
>                  add_to_dict(x)

This function changes the value of a global variable, *my_dict*. Using 
global variables is frowned upon. In this case, it would be much better 
to have the dictionary be local to the *prime_factor* function. After 
you've broken out of the *while* loop, just execute "return my_dict".

>                  tmp_n /= x
>                  break
>
>          if tmp_check == tmp_n: #number is prime...so just to add to
> dict
>              add_to_dict(tmp_n)
>              break

The only reason that the *tmp_check* variable exists is to test whether 
you fell out of the *for* loop without finding any divisors for *tmp_n*. 
A cleaner approach is to use the optional *else* clause of the *for* 
loop, which is executed only if you didn't *break* out of the loop:

     for x in range(2,int(ceil(sqrt(tmp_n)) + 1)):
         if tmp_n % x == 0:
             add_to_dict(x)
             tmp_n /= x
             break
     else:
         # tmp_n is prime...so just to add to dict
         add_to_dict(tmp_n)
         break


>
>
> def add_one(x):
>      return x+1
>
>
> def mul(x,y):
>      return x * y
>
> def add_to_dict(p_num):
>      if my_dict.has_key(p_num):
>          my_dict[p_num] += 1
>      else:
>          my_dict[p_num] = 1
>

As poster pruebauno pointed out, using a collections.defaultdict 
eliminates the need for the *add_to_dict* function.

>
> my_dict = {}
>
>
> prime_factors(135)
> l = map(add_one,my_dict.values())
> print reduce(mul, l, 1)

This may seem trivial, but ... don't use the single-character lowercase 
"l" as a variable. It looks too much like the digit "1" -- in some 
fonts, it looks identical!

FWIW, here's my implementation. It's much slower, because it doesn't use 
the square root optimization. It uses another optimization: when a prime 
factor is located, *all* of its occurrences are factored out at the same 
time.

#--------------------------------
from collections import defaultdict

def prime_factors(n):
     """Return the prime factors of the given number (>= 2)"""
     if n < 2:
         print "arg must be >= 2"
         return

     last_result = n
     factors = defaultdict(int)
     next_divisor = 2

     while True:
         while last_result % next_divisor == 0:
             factors[next_divisor] += 1
             last_result /= next_divisor
             if last_result == 1:
                 return factors
         next_divisor += 1
#--------------------------------


HTH,
John