Project Euler in R Problem 3

For this problem I had to find the largest prime factor of the number “600851475143”.

First I defined a function called “is.prime” to determine whether your input (is.prime(x)) is a prime number. To define this function, I used a for loop to test if the number is divisible by any number between 2 and the square root of the number. This follows from the fact that if you have two factors that multiply to a number “x”, only one can be greater than the square root of “x”.

If “x” is divisible by any number from 2 to sqrt(x) then the is.prime function will return 0. Otherwise, it will return 1 if “x” is prime. I had to add in a special case for x = 2 since 2 is divisible by 2 but it is still prime (since 2 is the only factor not equal to 1).

I then tested to see which values between 1 and sqrt(600851475143) were prime using a for loop and placed the 1 or 0 (corresponding to the is.prime function output) into a numeric vector named primes.

To see the actual prime numbers, I used the which function to give me the position of the 1s. Since my loop started at 1, the position corresponded to the actual numerical value of the number associated with that slot. I then filtered out the primes that divided 600851475143 into a separate vector and took the max of it.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
is.prime <- function(x) {
  prime <- 1
  for (i in 2:ceiling(x^.5))
  {
    if (x %% i == 0 && x != 2){
      prime <- 0
    }
    }
  return(prime)
}


huge <- 600851475143
n <- ceiling(huge^.5)
primes <- numeric(n)

for (i in 1:n) {
  primes[i] <- is.prime(i)
}

flag <- which(primes == 1)

Prime.Factors <- flag[which(huge %% flag ==0)]
max(Prime.Factors)

R took a little bit of time to run this loop. If anybody has any suggestions on how to optimize this script, I’d love to hear them.