Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.
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).
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.
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") |
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.