A more pythonish code

[prasad_chand]

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

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)
tmp_n /= x
break

if tmp_check == tmp_n: #number 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


my_dict = {}


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


Thanks for your time.

 

[nn]

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

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)
tmp_n /= x
break

if tmp_check == tmp_n: #number 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


my_dict = {}


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


Thanks for your time.

I did a quick refactoring for Python 3.1 (should mostly work in older
versions too):

from math import ceil, sqrt
from functools import reduce
from collections import defaultdict
from operator import mul

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)
"""
factors = defaultdict(int)
while n != 1:
for x in range(2,int(ceil(sqrt(n)) + 1)):
if n % x == 0:
factors[x] += 1
n /= x
break
else:
#number is prime...so just to add to dict
factors[int(n)] += 1
break
return factors

factors = prime_factors(135)
exponents = [x+1 for x in factors.values()]
print(reduce(mul, exponents, 1))

 

[John Posner]

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

 

[prasad_chand]

Hi Mr.Posner & nn,

Thank your for your time & effort. I never knew that for...ever
combination even existed. I would keep these insights in mind in the
future.

Thanks again,
Prasad

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