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  

Related Posts

• December 23, 2010 -- Project Euler — Problem 187 (2)
• November 1, 2011 -- Project Euler-Problem 38 (0)
• November 8, 2011 -- project euler-Problem 43 (0)
• June 21, 2011 -- ProjectEuler-Problem 46 (1)
• May 21, 2011 -- [Project Euler] – Problem 58 (4)