Project Euler — problem 3

May 27, 2012
By

(This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers)

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?

My solvement is straightforward: firstly to identify all the prime numbers between 2 and sqrt(n); secondly find out the prime factors of this number.

?View Code RSPLUS

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 ``` ```# helper function to determine whether a number is a prime is.prime <- function(x) { if (x == 1) { flag <- FALSE } if (x == 2 | x == 3) { flag <- TRUE } else { flag <- !any(x %% 2:(floor(sqrt(x))) == 0) } return(flag) } # generate all primes between 2 and sqrt(600851475143) large <- 600851475143 n <- floor(sqrt(large)) flag <- logical(n) for (i in 1:n) { flag[i] <- is.prime(i) } prime <- (1:n)[flag] # search for the prime factors of the large number prime.fac <- prime[(large %% prime) == 0] prime.max <- max(prime.fac) cat("The result is:", prime.max, "\n")```

Althought the idea is simple, the code was running slow. Two parts should be optimized: one is the is.prime() in which other fast primality testing could be applied; the other is the prime factor searching. For instance, I could search for prime factors less than 100; if there are, divide the large number by the factors; then continue to search for prime factors of the quotient larger than 100, say 100 ~ 500. That would be faster.

R-bloggers.com 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...

Tags: , ,