// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (21 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 3 Solution

Project Euler 3 Solution

Project Euler 3: Find the largest prime factor of a composite number


Project Euler 3 Problem Description

Project Euler 3: The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Analysis

Project Euler 3The question asks that if the the number 600851475143 was factored into its distinct prime factors, report the largest one found.

This can be done without the use of arrays or a giant list of prime numbers. Instead, we generate prospective prime numbers, p, through sieving. The list of candidates for p are the set of odd natural numbers {2, 3, 5, 7, 9, 11, 13, 15, …}.

The remainder, after removing all other prime factors, p, is the largest prime factor and we can terminate the loop when the current candidate’s square exceeds the residual value of n.

Finding the largest prime factor

p = 2
while (p*p <= n):      
  if (n % p == 0): 
    n //= p
  else: 
    p += 2 if p>2 else 1   # after 2, consider only odd p

Here's a trace of this algorithm to demonstrate the process of removing prime factors from 
the number n and leaving the largest prime factor p.
n=495
 p      p2   n
p=2 and 4 ≤ 495: 2 is not a factor so its skipped and p is incremented to 3
p=3 and 9 ≤ 495: 3 is a factor: n = 165
p=3 and 9 ≤ 165: 3 is a factor: n = 55
p=3 and 9 ≤ 55: 3 is not a factor so its skipped and p is incremented to 5
p=5 and 25 ≤ 55: 5 is a factor: n = 11
p=5 and 25 ≤ 55: 5 is not a factor so its skipped and p is incremented to 7
p=7 and 49 ≤ 55: 7 is not a factor so its skipped and p is incremented to 9
p=9 and 81 not ≤ 55: p is incremented to 11 and the while loop terminates.
The conditional of the while loop is checked after the loop's last statement.

If the given number, n, is already prime then n is returned as the largest prime factor, which is nice, because it is, in fact, itself the largest prime factor. Here’s a Javascript prime factor calculator to find all the prime factors of a number.

The HackerRank version ups the limit for n≤1012 and runs test cases up to 10 consecutive trials. This algorithm handles those test cases in less than a tenth of a second.

Project Euler 3
This program and method
solves all test cases for
Project Euler 3 on HackerRank

Project Euler 3 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 3 Solution Python 2.7 source.

Answer

Slowly swipe from either end beginning with the white vertical bar to get an idea of the starting or ending digits. For less drama, just double click the answer area. The distance between the two bars will give you an idea of the magnitude. Touch devices can tap and hold the center of the box between the two bars and choose define to reveal the answer.
|6857|

Afterthoughts

  • Trial division, used here, works well for smaller numbers less than 1021, for larger numbers there are several efficient algorithms available.

  • A more favorable method for factoring numbers under 100 digits long is the Quadratic sieve, a recent invention. It is a much simpler algorithm to implement compared to others and lends itself to parallelization. Because it is a sieve, large amounts of memory may be required.

  • Another is Pollard's Rho algorithm with improvements by Brent. It’s easy to program and fast for numbers with small factors.

  • To find the prime factors of any number see: prime factor calculator written in JavaScript.

  • Some other examples:
  • n = 600851475143, iterations:738
  • n = 600851475143600851475143, iterations:5006, largest prime factor: 99990001, <1 sec
  • n = 600856008514751431475143, iterations:11859442, largest prime factor: 562585074706409, <6 sec

Project Euler 3

Project Euler 3 Solution last updated

Discussion

No comments yet.

Post a comment