Wednesday 21 September 2011

Project Euler: problem 3


The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?


This one was quite easy, and much easier in R as it turns out.

The GNU Multi-Precision Library (GMP) is available as a package in R. So the only thing I had to do is install the library. Rest... well... not much...

library(gmp)
factorize(600851475143) 

# The factorize function lists down all the prime factors of the number in the parentheses in ascending order.


Answer: 6857


Well, I understand I did not do much here than just being aware of something called the GMP. Don't blame me, blame them or him. But in due respect for the only concrete language known to humankind (Math not R), I shall try to come up with a more genuine approach.

1 comment:

  1. Not as elegant but does the job:

    problem3 = function(number){

    sqnumber = sqrt(number)
    primes = 2:sqnumber
    i=1
    n1=2

    while(n1 < sqrt(sqnumber)){
    takeout = seq(n1,primes[length(primes)],by=n1)[-1]
    primes = primes[-which(primes %in% takeout)]
    i = i+1
    n1=primes[i]
    }

    return(max(primes[which(number %% primes == 0)]))

    }

    problem3(600851475143)

    ReplyDelete