Benjamin Van Nguyen

A place to hone our problem solving skills and enjoy eldritch art — and hopefully retain our sanity whilst doing so. I post a coding challenge every few days for us to solve together so subscribe at the very bottom of the page to receive email notifications :)

The Largest Prime Factor

And yet I saw them in a limitless stream—flopping, hopping, croaking, bleating—surging inhumanly through the spectral moonlight in a grotesque, malignant saraband of fantastic nightmare. And some of them had tall tiaras of that nameless whitish-gold metal . . . and some were strangely robed . . . and one, who led the way, was clad in a ghoulishly humped black coat and striped trousers, and had a man’s felt hat perched on the shapeless thing that answered for a head. . . .

What's on the menu today? Prime numbers. 

The Problem: Largest Prime Factor
 

The prime factors of 13195 are 5, 7, 13 and 29 — with the largest being 29. 

What is the largest prime factor of the number 600851475143 ?

 

I admit that this problem can be a little tricky; but as always, I recommend you give this problem a solid indvidual effort before reading my solution. If you'd like to see if your algorithm is correct, the answer is 6857.

Now before we encode the algorithm into Python, lets actually discuss the algorithm first. Now I'm sure most of you recall those cute little trees we all used to make in middle school when asked to find the prime factorization of a specific number. If not, here's a quick demonstration of how it works:
 

                        13195
                      /       \
                     5         2639
                              /    \
                             7      377
                                   /   \
                                 13     29

5 * 7 * 13 * 29 = 13195

 

Pretty self-explanatory right? Since the answer wants the largest prime factor of the given number, the answer for this particular example that they provided is 29. Now of course, figuring out the 5 was a factor of 13195 was pretty simple; but figuring out the factors of 377 isn't as trivial — unless I'm some sort of genius. Unfortunately for most of us (me included), we are not geniuses; so we have to come up with cool algorithms to feed into a computer which can run them unfathomably faster than we can. So what is this algorith in which I speak? Lets dive in. 

Finding the factors of a number is just one gigantic exercise in trial & error. Given a number such as 13195, here are sample steps showing how we would search for factors algorithmically. We're going to be utilizing the modulo operator.

  1. 13195 % 2 is not equal 0.
  2. 13195 % 3 is not equal 0. 
  3. etc. etc. 
  4. 13195 % 5 is equal to 0.

Woot! This means that 5 is one of our factors. Lets write it down somewhere (perhaps store in a list wink wink) and keep going! We're going to divide 13195 by 5 and get 2639, and find its factors. Notice, by the way, how we didn't start by doing % 1 — that's simply because 1 is a factor of everything and is thus, uninteresting. 

  1. 2639 % 6 is not equal 0. 
  2. 2639 % 7 is equal to 0.

We got our next factor! Lets write that one down too! I think you can pretty much see what we're getting at here. Verbally, here's how our algorithm plays out thus far

  1. Check to see if "i" is a factor of our given number. 
  2. If no, pass; if yes, save it and divide our given number by i. Our given number has now changed value. 
  3. Increment "i" by +1
  4. Repeat steps 1 through 3. 

"But wait, how do we know when to terminate the algorithm???" Good question! Recall how we've been saving all of the factors along the way? Perhaps we should terminate the algorithm when a certain condition as been met — perhaps when the product of all of our saved factors equal the original given number. What does this imply? A WHILE-LOOP OF COURSE!

Whenever I want a process to repeat itself until a certain condition is met, I'll heavily consider while-loops. Now lets start encoding our algorithm into Python. 

 


# We said we would use a list to save all the factors we saved along the way. 

def prime(n):

    factors = [1] # List where we'll store all of our factors. 
    i = 2 # This is the first number we'll check to see if it's a factor of n. 
    current = n 
    
    # Now what? 

# We initialized our list with 1 in it for two reasons:
# 1. 1 is a factor of everything. 
# 2. You'll see shortly. 
    

 

Now we need to set up our while-loop to run until the condition we spoke of earlier is met; that condition being when the product of all items in the list, factors, equals the original number, n. It will be auspicious to create a helper function to facilitate this. 

 

def product(li):
    result = 1 
    for i in li:
        result *= i # Multiply result by every element in the list.
    return result 

 

Now that we have our helper function, lets complete the algorithm. 

 

def product(li):
    result = 1
    for i in li:
        result *= i
    return result

def largest_prime(n):

    factors = [1]
    i = 2
    current = n

    while product(factors) != n: # Keeps running until product of all factors equals orig. number.
        if current % i == 0: # If i is a factor of the current number,
            factors.append(i) # append the integer assigned to i to our list, factors.
            current //= i # Divide (integer division) our current number by that factor.
        i += 1 # Increment i by +1 to check the next number

    return factors[-1] # When loop ends return the last element of the list, which is the greatest.

 

And there you have it!

 

Now you could be cool and use the reduce function from the functools module along with lambda functions to avoid the use of a helper function, but you'll find that performance is pretty much the same. I'll let you figure out why. Hint: How would you implement the reduce function? 

And for those of you unfamiliar with reduce and lambda functions, we'll be using it very soon so stick around! Anyway, for those of you curious, below you'll find the second way of doing the exact same thing in pretty much the same amount of time. 

 

from timeit import Timer
from functools import reduce

def product(li):
    result = 1
    for i in li:
        result *= i
    return result

def largest_prime_1(n):

    factors = [1]
    i = 2
    current = n
    while product(factors) != n:
        if current % i == 0:
            factors.append(i)
            current //= i
        i += 1
    return factors[-1]

def largest_prime_2(n):

    factors = [1]
    i = 2
    current = n
    while reduce(lambda x, y: x * y, factors) != n:
        if current % i == 0:
            factors.append(i)
            current //= i
        i += 1
    return factors[-1]

num = 600851475143

t1 = Timer(f"largest_prime_1({num})", "from __main__ import largest_prime_1")
print(f"largest_prime_1: {t1.timeit(number=1000)} milliseconds")

t2 = Timer(f"largest_prime_2({num})", "from __main__ import largest_prime_2")
print(f"largest_prime_2: {t1.timeit(number=1000)} milliseconds")

# largest_prime_1: 3.5543122609999998 milliseconds
# largest_prime_2: 3.5686384970000002 milliseconds

 

And just for fun, here it is my solution in Javascript:

 

function largest_prime_1(n) {
  var factors = [1];
  var i = 2;
  var current = n;

  while (factors.reduce((x, y) => x * y) !== n) {
    if (current % i === 0) {
      factors.push(i);
      current /= i;
    };
    i++;
  };
  return factors[factors.length - 1]
};


If you guys have any question post below, or email me at callofcthoder@gmail.com :) 

 


Join the discussion:

Log in or Sign up to vote and leave comments.


solidiquis | May 18, 2019, 1:17 a.m.
I just wondered if you've planned any effective marketing yet for your site this year. I'm self-employed achieving this for various businesses for numerous years now, I feed my family doing this so I won't complain. I've a means of getting immediate interested traffic and buyers to your website through social media marketing channels and email. As well as getting more likes, followers for all your social media accounts. I've a new program that has just been completed that listens to all social mentions being made, if your certain word or phrase is detected, we instantly send back to them a message that they should visit your site. We are able to use as much search terms as we would like, hundreds of targeted visits a day. I can also help you to make/update your site, fix site errors add updates etc. If you might need it. Along with that, I'd also like to discover what your competitors have implimented that you havn't done yet and address those issues asap. I'd also like to make a video or 2 about your website and get them to rank high pretty quickly. Lastly I have a big database of opt in customers which are enthusiastic about what it is you do, so if you'd prefer to expand your overall newsletter list let me know, I can get you these records whenever you'd like them. They'd enable you to get instant leads by supplying you with a listing of people or businesses that are seeking just what it is you're offering. I take advantage of tools a good number of individuals don't know about or don't have time to use for themselves and I would like to use them on your site. If your're to busy with current clients I understand, I was just wondering was all. Let me know if you'd like more info or references, I have more than I know what to do with. Winston 1.319.423.9473
2 | Reply

Subscribe to be notified about new blog entries!

Email