# Euler Problem 3: Largest Prime Factor

**The Devil is in the Data**, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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

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

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

**leave a comment**for the author, please follow the link and comment on their blog:

**The Devil is in the Data**.

R-bloggers.com offers

**daily e-mail updates**about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.

Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.