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.
Hey, You have a website callofcthoder.com, right? Of course you do. I am looking at your website now. It gets traffic every day – that you’re probably spending $2 / $4 / $10 or more a click to get. Not including all of the work you put into creating social media, videos, blog posts, emails, and so on. So you’re investing seriously in getting people to that site. But how’s it working? Great? Okay? Not so much? If that answer could be better, then it’s likely you’re putting a lot of time, effort, and money into an approach that’s not paying off like it should. Now… imagine doubling your lead conversion in just minutes… In fact, I’ll go even better. You could actually get up to 100X more conversions! I’m not making this up. As Chris Smith, best-selling author of The Conversion Code says: Speed is essential - there is a 100x decrease in Leads when a Lead is contacted within 14 minutes vs being contacted within 5 minutes. He’s backed up by a study at MIT that found the odds of contacting a lead will increase by 100 times if attempted in 5 minutes or less. Again, out of the 100s of visitors to your website, how many actually call to become clients? Well, you can significantly increase the number of calls you get – with ZERO extra effort. TalkWithCustomer makes it easy, simple, and fast – in fact, you can start getting more calls today… and at absolutely no charge to you. CLICK HERE http://www.talkwithcustomer.com now to take a free, 14-day test drive to find out how. Sincerely, Eric PS: Don’t just take my word for it, TalkWithCustomer works: EMA has been looking for ways to reach out to an audience. TalkWithCustomer so far is the most direct call of action. It has produced above average closing ratios and we are thrilled. Thank you for providing a real and effective tool to generate REAL leads. - P MontesDeOca. Best of all, act now to get a no-cost 14-Day Test Drive – our gift to you just for giving TalkWithCustomer a try. CLICK HERE http://www.talkwithcustomer.com to start converting up to 100X more leads today! If you'd like to unsubscribe click here http://liveserveronline.com/talkwithcustomer.aspx?d=callofcthoder.com
2 | Reply

Subscribe to be notified about new blog entries!

Email