Project Euler — problem 5

May 30, 2012
By

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

I spent around 40 minutes on the last post yesterday, which delayed my bedding time and caused my sleepiness in the morning. So, I’m starting to write earlier tonight. The fifth problem is to calculate the smallest composite for given numbers.

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

I used a “old-fashioned” way in the first place. Identify the primes less than 20; determine the prime factor(s) for each number; find out the maximum for each prime factor; then multiply each prime factor multiple times as many as the maximum. Well, this sounds hard to understand. But the codes are more straightforward (a little long, so I collapse it).

?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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
is.prime <- function(x) { 
  if (x == 1) {
    flag <- FALSE
  } 
  else if (x == 2 | x == 3) {
    flag <-  TRUE
  } 
  else {
    flag <- !any(x %% 2:(floor(sqrt(x))) == 0)
  }
  return(flag)
}
n <- 20
flag <- logical(n)
for (i in 1:n) {
  flag[i] <- is.prime(i)
}
prime <- (1:n)[flag]
 
prime.fac <- function(x, prime = prime) {
  # helper function for prime factors calculation
  m <- length(prime)
  fac.count <- numeric(m)
  for (i in 1:m) {
    x <- x
    prime.num <- prime[i]
    if (x %% prime.num == 0) {
      fac.count[i] <- 1
      x = x / prime.num
      while (x %% prime.num == 0) {
        fac.count[i] <- fac.count[i] + 1
        x = x / prime.num
      }
    }  
  }
  return(fac.count)
}
 
# built a matrix to store the numbers of prime factors 
mat <- matrix(0, nrow = n-1, ncol = length(prime), 
              dimnames = list(num = 2:n, prime = prime))
for (i in 2:n) {
  mat[(i-1), ] <- prime.fac(i, prime)
}
max.count <- apply(mat, 2, max)  ## find out the maximum of each prime factor
result <- prod(prime ^ max.count)
cat("The result is:", result, "\n")

There are other ways to solve this problem. I came up to another solution before lunch today (my mind kinda runs faster before meals). Given a series of numbers, save the first one temporarily as your result (you can pick any one number as the first, just line the numbers up). The next step is the key – use the next number to divide this temporary result, if the remainder is zero, it means this result is the smallest number that can be divided by these two numbers and you can move on; if the remainder is not zero, you need figure out the remainder multiply which number X could be divided by the second given number without remainder. Then multiply the temporary result with the number X, resulting a new number which is the smallest composite for the first two numbers. The following is simple — just repeat above two steps till the last number. The for loop function can do the work for you.

?View Code RSPLUS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
small.composite <- function(n) {
  composite <- 1
  for (i in 1:n) {
    remain <- (composite %% i)
    if (remain != 0) {
      if (i %% remain == 0) {
        composite <- composite * i / remain
      }
      else {
        composite <- composite * i
      }
    }
  }
  return(composite)
}
cat("The result is:", small.composite(20), "\n")

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.