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

This code on GitHub.

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

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

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

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

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

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