algorithm - Largest Prime Factor Ruby using Fermat's factorization method -

i have code seems working number 6-8 digits, in normal time period. when enter bigger values amount ridiculously bug. takes more 4 hours complete. here code.

#fermat's factorization method  def get_largest_prime n     t=(math.sqrt(n)+1).floor     k=0     prime_numbers=[]     while (t+k)<n         element = (t+k)**2-n         if is_integer? math.sqrt(element)             #store prime numbers             prime_numbers << t+k+math.sqrt(element)             prime_numbers << t+k-math.sqrt(element)              #puts "prime factors of #{n} are: #{t+k+math.sqrt(element)} , #{t+k-math.sqrt(element)}"         end         k+=1     end   puts "prime factors: "+prime_numbers.to_s  end  #making sure 450.0 450, example. def is_integer? number     number.to_i == number ? true : false end  get_largest_prime 600851475143  

running take more 4 hours.

but running value ' 600851' example or ' 60085167' not take lot of time. ?

first note fermat factorisation doesn't give prime factors in general.

then, run until t+k >= n, means run while loop n - t times, since t sqrt(n), o(n) algorithm. largish n 600851475143 (about 6*10^11), bound take long.

you need change algorithm. when have found pair of divisors (both larger 1), factorise them both recursively. if smaller of found factors 1, prime factor.

doing (forgive bad style, barely know ruby):

#fermat's factorization method  def get_largest_prime n     t=(math.sqrt(n)+1).floor     k=0     prime_numbers=[]     while (t+k)<n         element = (t+k)**2-n         if is_integer? math.sqrt(element)             #store prime numbers             = t+k+math.sqrt(element)             b = t+k-math.sqrt(element)             if b == 1                 prime_numbers <<                 break             end             prime_numbers += get_largest_prime             prime_numbers += get_largest_prime b             break             #puts "prime factors of #{n} are: #{t+k+math.sqrt(element)} , #{t+k-math.sqrt(element)}"         end         k+=1     end   return prime_numbers end  #making sure 450.0 450, example. def is_integer? number     number.to_i == number ? true : false end  = get_largest_prime 600851475143 puts "prime factors: "+a.to_s 

solves given problem quickly.

however, still take long time numbers have no divisors close square root.

the standard factorisation trial division has better worst-case behaviour (o(sqrt(n) worst case). mixed approach can faster pure trial division, though.