CODEWITHSUNDEEP
ruby
tamatojuiice
tamatojuiice

Reputation: 11

Project Euler #3 in Ruby

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 ?

def is_prime?(number)
    prime = true
    (2...number).each { |x|
        prime = false if number % x == 0
    }
    prime
end

def largest_prime(number)
    primes = []
    (number.downto(1)).each {|x|
        primes.push(x) if number % x == 0 && is_prime?(x)
        break if primes.count == 1
    }
    primes[0]
end

My answer is written in Ruby. The code works for smaller numbers but not larger, can anyone explain what exactly is going on and how to get around it? I've seen other people with this issue -- sorry to repost -- but I'm a programming newb and I don't truly understand their answers, also haven't seen any other posts answering in Ruby. Thanks!

Upvotes: 1

Views: 1956

Answers (6)

the_prole
the_prole

Reputation: 8985

This is the simplest algorithm I could find

def lpf(n)
  i = 2
  while i * i <= n
      while n % i == 0
          n = n / i
          break if n == i
      end
      i += 1
  end
  n
end

p lpf(600851475143) # => 6857

Upvotes: 0

Valentin Miculit
Valentin Miculit

Reputation: 439

It can also be solved by division as follows:

def largest_prime(number)
i = 2
largest_divisor = 0
  while i < number
    if number % i == 0
      largest_divisor = i
      number = number / i
      i = 2
    else
      i += 1
    end
  end
number
end

Upvotes: 1

emil
emil

Reputation: 1

        t = Time.now

class Fixnum
    def add
        X[ X.length ] = self
    end

    def prime
    prime = true
        i = 0
        k = Math.sqrt(self)
        while (k >= X[i]) do            
            if self % X[i] == 0 then
                prime = false
                break
            end
            i +=1
        end
        if prime then
            self.add
        end
        return prime
    end

    def prime2 
      prim =true
      2.upto(Math.sqrt(self)) do
       |i|
       if self % i == 0 then
        prim =false
        break
       end
      end  
      return prim
     end    
end

################ Here the code starts:
X = []
2.add

3.upto(10000) { |i| i.prime}

a = 600851475143
i = 0
while a != 1 do
    if (a % X[i] == 0) then 
        while a % X[i] == 0 do
            a = a / X[i]
        end
    else
        i +=1
    end
end
puts X[i]

result = 6857
14.219256 ms

Upvotes: 0

Chris Yeung
Chris Yeung

Reputation: 2723

I think this will even be better:

require 'prime'
puts Prime.prime_division(600851475143).last[0]

Upvotes: 1

dahal
dahal

Reputation: 94

How about this:- 

require "prime"

def problem_three(num)
    last_prime = num.prime_division.last # This will give us [6857, 1]
    # We only want the first one
    last_prime[0] # or last_prime.first
end

puts problem_three(600851475143)

The answer would be:- 

$ ruby problem_three.rb
  6857

Upvotes: 1

Stoic
Stoic

Reputation: 10754

Here are some pointers to help you improve the performance of your code (assume your test number is n):

  • Only perform the divisibility test from 2 to the square_root(n). Any number greater than square_root(n) has already been covered, in this range. Think mathematically :)
  • Any even number, which is not 2 is not a prime!
  • Use a prime sieve to greatly increase the performance of your prime testing algorithm.

But, do not do this:

  • Since, you are solving Euler problems for fun and learning, do NOT use the prime library that ruby provides.

Here are the two helpers, I have used, for solving this problem (I wrote them long back when I was new to ruby, and may not be that efficient, e.g. they don't use the sieve I advised):

def lower_divisors_of(n)
  data = (2..(Math.sqrt(n).to_i)).select{ |a| n % a == 0 }
  data.map{|a| [a, n/a]}.flatten.sort.reverse
end

def is_prime?(n)
  lower_divisors_of(n).empty?
end

lower_divisors_of(n).detect{|i| is_prime?(i)}

Upvotes: 5

Related Questions