prasad_chand
2/26/2010 10:02:00 AM
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
On Feb 25, 10:57 pm, John Posner <jjpos...@optimum.net> wrote:
> 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