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 third problem:

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.

To leave a comment for the author, please follow the link and comment on his blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: visualization (ggplot2, Boxplots, maps, animation), programming (RStudio, Sweave, LaTeX, SQL, Eclipse, git, hadoop, Web Scraping) statistics (regression, PCA, time series, trading) and more...



If you got this far, why not subscribe for updates from the site? Choose your flavor: e-mail, twitter, RSS, or facebook...

Tags: , ,

Comments are closed.