R Examples

R Program - Find the largest prime factor of a number

Objective: Find the largest prime factor of a number in an efficient way.

To find the largest prime factor is a very simple concept. Lets say the number is 1092. All prime factors of 1092 are 2, 2, 3, 7, 13. Hence, the largest prime factor is 13. To find this, the following algorithm can be used:

  number = num

  Step 1: If num is divisible by 2, store
  largest prime factor as 2. keep on dividing
  num until it is not divisible by 2. After
  each division, update num as num/2.

  Step 2: At this point, num must be odd.
  Starting with 3 to square root of num, if
  divisible, divide and update num, and update
  largest prime factor.

  Step 3: if the modified num is greater than
  2, update the largest prime factor with num.

Finding the largest prime factor of a number

The example below illustrates the above algorithms.

MaxPrime <- function(num) {
  CurrMaxPrime <- -1

  #If num is divisible by 2, store CurrMaxPrime
  #as 2. keep on dividing num until it is not 
  #divisible by 2. After each division, update 
  #num as num/2.
  if(num %% 2 == 0) {
    CurrMaxPrime <- 2
    while(num %% 2 == 0) {
      num <- num/2    
    }
  }

  #At this point, num must be odd. Starting with 
  #3 to square root of num , if divisible, divide 
  #and update num, and update CurrMaxPrime
  for (i in seq(3, as.integer(sqrt(num)), 2)) {
    while(num %% i == 0) {
      CurrMaxPrime <- i
      num <- num/i      
    }    
  }

  #if the modified num is greater than 2, 
  #update the CurrMaxPrime with num 
  if (num > 2) {
    CurrMaxPrime <- num
  }

  return (CurrMaxPrime)
}


x <- 42
y <- 1092
z <- 695467363456

cat("Largest prime factor of", x, "is:", 
    MaxPrime(x), "\n")
cat("Largest prime factor of", y, "is:", 
    MaxPrime(y), "\n")
cat("Largest prime factor of", z, "is:", 
    MaxPrime(z), "\n")

The above code will give the following output:

Largest prime factor of 42 is: 7 
Largest prime factor of 1092 is: 13 
Largest prime factor of 695467363456 is: 5433338777