project euler - problem 47

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  
p5rn7vb

Related Posts

Leave a Comment


NOTE - You can use these HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>