Euler Problem 3: Largest Prime Factor

Euler Problem 3 Definition

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

Generating Prime Numbers

This solution relies on two functions that can be used for multiples problems. The Sieve of Eratosthenes generates prime numbers from 2 to n. The code is commented to explain the sieve and the image shows how numbers from 1 to 100 are sieved to find the primes.

Sieve of Eratosthenes.

Sieve of Eratosthenes. Green are multiples of 2, Blue are multiples of 3, the orange coloured numbers are multiples of 5 and purple the multiples of 7. The remaining numbers (except 1) are the prime numbers (black).

The prime.factors function generates the list of unique prime divisors and then generates the factors. The factors are identified by dividing the number by the candidate prime factors until the result is 1.

Solution

# Sieve of Eratosthenes for generating primes 2:n
esieve <- function(n) {
    if (n==1) return(NULL)
    if (n==2) return(n)
    # Create a list of consecutive integers {2,3,…,N}.
    l <- 2:n
    # Start counter
    i <- 1
    # Select p as the first prime number in the list, p=2.
    p <- 2
    while (p^2<=n) {
        # Remove all multiples of p from the l.
        l <- l[l == p | l %% p!= 0]
        # set p equal to the next integer in l which has not been removed.
        i <- i + 1 # Repeat steps 3 and 4 until p2 > n, all the remaining numbers in the list are primes
        p <- l[i]
    }
    return(l)
}

# Prime Factors
prime.factors <- function (n) {
    factors <- c() # Define list of factors
    primes <- esieve(floor(sqrt(n))) # Define primes to be tested
    d <- which(n%%primes == 0) # Idenitfy prime divisors
    if (length(d) == 0) # No prime divisors
        return(n)
    for (q in primes[d]) { # Test candidate primes
        while (n %% q == 0) { # Generate list of factors
            factors <- c(factors, q)
            n <- n/q } } if (n > 1) factors <- c(factors, n)
    return(factors)
}

max(prime.factors(600851475143))

The solution can also be found by using the primeFactors function in the numbers package. This package provides a range of functions related to prime numbers and is much faster than the basic code provided above.

library(numbers)
max(primeFactors(600851475143))

This code on GitHub.

6 thoughts on “Euler Problem 3: Largest Prime Factor

  1. Pingback: Euler Problem 10: Summation of Primes - Use-R!Use-R!

  2. Pingback: Euler Problem 10: Summation of Primes – Mubashir Qasim

  3. Pingback: Euler Problem 12: Highly Divisible Triangular Number | The Devil is in the DataThe Devil is in the Data

  4. Pingback: Euler Problem 12: Highly Divisible Triangular Number - Use-R!Use-R!

  5. Pingback: Euler Problem 10: Summation of Primes | The Devil is in the Data

  6. Pingback: Generating Quadratic Primes: Euler Problem 27 | The Devil is in the Data

Feel free to share your thoughts about this article