1

I am unable to understand the following block of code which I came across this site itself. It creates a function to find out the largest prime factor of a given number. It is given below:

def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
    while n % d == 0:
        factors.append(d)
        n /= d
    d = d + 1

return factors
pfs = prime_factors(1000)
largest_prime_factor = max(pfs) # The largest element in the prime

My doubt is that the function prime_factors(n) would return the factors of n and not the prime factors, since the while loop is only checking if d is a factor of n and not if it is also a prime as it should be.

Please point out if I'm wrong and also the reasoning behind your logic. Furthermore, if I'm correct, then kindly provide a suitable block of code and the logic behind it in simple terms. Try to keep the code as simple as possible.

smci
  • 32,567
  • 20
  • 113
  • 146
Aradhye Agarwal
  • 439
  • 1
  • 4
  • 9
  • 2
    Here's how I would approach this problem. Step 1: I'd run the program with examples, and see if it produces factors or prime factors. Step 2: when I discover my guess is wrong (and the program does work as advertised), I'd run through the program myself with small numbers (n=4, n=6, n=18 might be interesting ones) and see what's going on. – Paul Hankin May 13 '16 at 04:59

2 Answers2

2

Note that in the inner loop, n is divided by d while iteration.

while n % d == 0:
    factors.append(d)
    n /= d

That means, after each iteration, it's impossible for the new value of n to be divisible by d any more.

Take an example, let's say n = 3000, it has a factor 15 that isn't a prime number. However, because n is passed by d = 3 and d = 5 first, by the time d reaches 15, n would have been a number that's neither divisible by 3 nor 5, so the non-prime factor 15 would not pass n % d == 0 now.

Yu Hao
  • 119,891
  • 44
  • 235
  • 294
2

This function is correct, pay attention to the second while block. It will continuously divide the given number by the d variable, when the result of the division has a remainder, it will leave this block and increment d by one, then it will run again.

Having that in mind, this function will divide the number by 2 as many times it can without leaving a remainder, then it will move to the next number that doesn't leave remainders. In the end the result will only contain prime numbers.

It'll go like this:

def prime_factors(n):
   factors = []
   d=2
   while n > 1:
     while n % d == 0:
       factors.append(d)
       n /= d
     d += 1
   return factors

print(prime_factors(1000)) # will print [2, 2, 2, 5, 5, 5]
Bruno Castro
  • 233
  • 2
  • 6