Site icon R-bloggers

project euler – problem 47

[This article was first published on YGC » 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 first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7
15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct primes factors. What is the first of these numbers?


getFactor <- function(n) {
    f <- c()
    for ( i in 2:ceiling(sqrt(n/2)))  {
        if (n %%i ==0) {
            n <- n/i
            while(n %% i ==0) {
                n <- n/i
            }
            f <- c(f,i)
            if (gmp::isprime(n) !=0) {
                f <- c(f,n)
            }
        }
    }
    return(unique(f))
}



i <- 4
n <- 10^(i-1)

while(TRUE) {
    flag <- 0
    for (j in 0:(i-1)) {
        f <- getFactor(n+j)
        if(length(f) != i)
            break
        if(any(gmp::isprime(f) == 0))
            break
        if (j==i-1)
            flag <- 1
    }
    if (j == i-1 && flag==1) {
        print(n)
        break
    }
    n <- n+j+1
}

when i = 2, the program will print 14, and when i = 3, it will print 644.
This program is not hard coded, i can be set to any number to find the number that satisfy the property of problem 47 wanted.

> system.time(source("Problem47.R"))
[1] 134043
   user  system elapsed 
  43.22    0.00   43.28  

Related Posts

To leave a comment for the author, please follow the link and comment on their blog: YGC » 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.