I am working on this challenge: "The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?" and my solution is clearly terrible! It takes about 10 seconds to produce this answer (which is correct), and when I tried to plug in the number 600851475143 (which is what they want), it actually crashe…

gistfile1.txt

def is_prime(int)
  i = 2
	while i < int
		if int % i == 0
			return false
			i = int
		end
		i += 1
	end
end

def prime_factor(max_num)
	full_array = []
	3.upto(max_num) do |num|
		if is_prime(num) != false
			if max_num % num == 0
				full_array << num
			end
		end
	end
	full_array.last
end

puts prime_factor(13195)

Hi!
Your is_prime function can be optimized heavily. First do a check if your number is even. If it is return false. Then you can start at 3 (i=3) and always add 2 to it (i += 2). Also it is enough to only check numbers which are smaller then the square root of your int. So you can write (while i*i < int). Don't ask me about the details. You can read about it in number theory. Although it will run faster that way, it won't do it for this problem i think. For a big speedup you can use a prime sieve which helps dramatically (see http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes as an example)

With the sieve you have an array of all primes (to a certain limit ofc) so you can access them much easier and faster, so you can optimize your prime_factor function with it