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

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=""> <s> <strike> <strong>