Project Euler Q3 :: Largest prime factor

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

so 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 29

but 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 range
prime.factors(600851475143) ## Error: cannot allocate vector of size 4476.7 Gb
## Error in prime.factors(600851475143): long vectors not supported yet: eval.c:6387

Sure enough, that’s bigger than the machine precision integer allows

as.numeric("600851475143") > .Machine$integer.max
## [1] TRUE

so, 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 486847
factors.prime <- sapply(factors, is.prime)
primes <- factors[factors.prime] 
z == prod(primes)
## [1] TRUE
max(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


rstats 

See also