Reputation: 11
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
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
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
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
Reputation: 2723
I think this will even be better:
require 'prime'
puts Prime.prime_division(600851475143).last[0]
Upvotes: 1
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
Reputation: 10754
Here are some pointers to help you improve the performance of your code (assume your test number is n
):
2
to the square_root(n)
. Any number greater than square_root(n)
has already been covered, in this range. Think mathematically :)2
is not a prime!But, do not do this:
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