Explanation. Standard caveat: don’t look here if you are trying to do these yourself.
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143?
It seems so simple at first glance, until of course you look at how big that last number is. I started off by making sure I understood the issue.
## check the worked solution
5*7*13*29## [1] 13195so far so good. At this point I realised that there isn’t an inbuilt is.prime so I stole one from this site.
is.prime <- function(num) {
if (num == 2L) {
TRUE
} else if (any(num %% 2L:(num-1L) == 0L)) {
FALSE
} else {
TRUE
}
}Testing the example works pretty well…
## let's loop up to n and list the prime factors
prime.factors <- function(n) {
primes <- c()
for(i in 1:n) {
## take advantage of lazy logical evaluation
## and short-cut to only the factors
if(n %% i == 0 & is.prime(i)) primes <- c(primes, i)
}
return(primes)
}
prime.factors(13195)## [1] 5 7 13 29but I hit a snag when I tried to do the same for the problem value.
w <- as.integer(600851475143)## Warning: NAs introduced by coercion to integer rangeprime.factors(600851475143) ## Error: cannot allocate vector of size 4476.7 Gb## Error in prime.factors(600851475143): long vectors not supported yet: eval.c:6387Sure enough, that’s bigger than the machine precision integer allows
as.numeric("600851475143") > .Machine$integer.max## [1] TRUEso, I abandoned the pre-filled list of values and went again with the brute force. For the sake of speeding it up, I delayed testing for primes until later, as I can do that over the generated list with an apply and only bothered testing the values below sqrt(n) and n/f where f is the largest found prime so far.
## lists are too big. Find the primes by brute force
## using floating point representations
z <- as.numeric("600851475143")
i <- 2
factors <- 1
## loop through values of i that are
## less than sqrt(z) and
## less than z/the largest found factor
while(i < sqrt(z) & i < z/max(factors)) {
## skip the prime test for now
if(z %% i == 0) factors <- c(factors, i)
i <- i + 1
}
factors## [1] 1 71 839 1471 6857 59569 104441 486847factors.prime <- sapply(factors, is.prime)
primes <- factors[factors.prime]
z == prod(primes)## [1] TRUEmax(primes)## [1] 6857### CORRECT
devtools::session_info()
## ─ Session info ──────────────────────────────────────────────────────────
## setting value
## version R version 3.5.2 (2018-12-20)
## os Pop!_OS 19.04
## system x86_64, linux-gnu
## ui X11
## language en_AU:en
## collate en_AU.UTF-8
## ctype en_AU.UTF-8
## tz Australia/Adelaide
## date 2019-08-13
##
## ─ Packages ──────────────────────────────────────────────────────────────
## package * version date lib source
## assertthat 0.2.1 2019-03-21 [1] CRAN (R 3.5.2)
## backports 1.1.4 2019-04-10 [1] CRAN (R 3.5.2)
## blogdown 0.14.1 2019-08-11 [1] Github (rstudio/blogdown@be4e91c)
## bookdown 0.12 2019-07-11 [1] CRAN (R 3.5.2)
## callr 3.3.1 2019-07-18 [1] CRAN (R 3.5.2)
## cli 1.1.0 2019-03-19 [1] CRAN (R 3.5.2)
## crayon 1.3.4 2017-09-16 [1] CRAN (R 3.5.1)
## desc 1.2.0 2018-05-01 [1] CRAN (R 3.5.1)
## devtools 2.1.0 2019-07-06 [1] CRAN (R 3.5.2)
## digest 0.6.20 2019-07-04 [1] CRAN (R 3.5.2)
## evaluate 0.14 2019-05-28 [1] CRAN (R 3.5.2)
## fs 1.3.1 2019-05-06 [1] CRAN (R 3.5.2)
## glue 1.3.1 2019-03-12 [1] CRAN (R 3.5.2)
## htmltools 0.3.6 2017-04-28 [1] CRAN (R 3.5.1)
## knitr 1.24 2019-08-08 [1] CRAN (R 3.5.2)
## magrittr 1.5 2014-11-22 [1] CRAN (R 3.5.1)
## memoise 1.1.0 2017-04-21 [1] CRAN (R 3.5.1)
## pkgbuild 1.0.4 2019-08-05 [1] CRAN (R 3.5.2)
## pkgload 1.0.2 2018-10-29 [1] CRAN (R 3.5.1)
## prettyunits 1.0.2 2015-07-13 [1] CRAN (R 3.5.1)
## processx 3.4.1 2019-07-18 [1] CRAN (R 3.5.2)
## ps 1.3.0 2018-12-21 [1] CRAN (R 3.5.1)
## R6 2.4.0 2019-02-14 [1] CRAN (R 3.5.1)
## Rcpp 1.0.2 2019-07-25 [1] CRAN (R 3.5.2)
## remotes 2.1.0 2019-06-24 [1] CRAN (R 3.5.2)
## rlang 0.4.0 2019-06-25 [1] CRAN (R 3.5.2)
## rmarkdown 1.14 2019-07-12 [1] CRAN (R 3.5.2)
## rprojroot 1.3-2 2018-01-03 [1] CRAN (R 3.5.1)
## sessioninfo 1.1.1 2018-11-05 [1] CRAN (R 3.5.1)
## stringi 1.4.3 2019-03-12 [1] CRAN (R 3.5.2)
## stringr 1.4.0 2019-02-10 [1] CRAN (R 3.5.1)
## testthat 2.2.1 2019-07-25 [1] CRAN (R 3.5.2)
## usethis 1.5.1 2019-07-04 [1] CRAN (R 3.5.2)
## withr 2.1.2 2018-03-15 [1] CRAN (R 3.5.1)
## xfun 0.8 2019-06-25 [1] CRAN (R 3.5.2)
## yaml 2.2.0 2018-07-25 [1] CRAN (R 3.5.1)
##
## [1] /home/jono/R/x86_64-pc-linux-gnu-library/3.5
## [2] /usr/local/lib/R/site-library
## [3] /usr/lib/R/site-library
## [4] /usr/lib/R/library