Euler Problem 3: Largest Prime Factor

December 14, 2016

(This article was first published on The Devil is in the Data, and kindly contributed to R-bloggers)

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.


# 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]

# 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
    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)


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.


The post Euler Problem 3: Largest Prime Factor appeared first on The Devil is in the Data.

To leave a comment for the author, please follow the link and comment on their blog: The Devil is in the Data. offers daily e-mail updates about R news and tutorials on topics such as: Data science, Big Data, R jobs, visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...

If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Comments are closed.

Search R-bloggers


Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)