Project Euler — problem 3

[This article was first published on Tony's bubble universe » R, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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 their blog: Tony's bubble universe » R.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)