Project Euler #3 in Ruby Solution Times Out

Project Euler #3 Ruby Solution - What is wrong with my code?

"premature optimization is (the root of all) evil". :)

Here you go right away for the (1) biggest, (2) prime, factor. How about finding all the factors, prime or not, and then taking the last (biggest) of them that is prime. When we solve that, we can start optimizing it.

A factor a of a number n is such that there exists some b (we assume a <= b to avoid duplication) that a * b = n. But that means that for a <= b it will also be a*a <= a*b == n.

So, for each b = n/2, n/2-1, ... the potential corresponding factor is known automatically as a = n / b, there's no need to test a for divisibility at all ... and perhaps you can figure out which of as don't have to be tested for primality as well.

Lastly, if p is the smallest prime factor of n, then the prime factors of n are p and all the prime factors of n / p. Right?

Now you can complete the task.

update: you can find more discussion and a pseudocode of sorts here. Also, search for "600851475143" here on Stack Overflow.

Ruby - Project Euler #23 Taking too long to run

You should try caching your results - if you already calculated if 13453 is a prime, you don't have to check it again:

@cache = {}
def check(n)
  if @cache[n].nil?
    s=0
    for i in (1..(n/2)+1)
      if n % i == 0 then
        s+=i
      end
    end

    @cache[n] = s>n
  end
  @cache[n]
end

def abundant()
  sum = 0
  for j in (1..28123)
    for k in (1..28123)
      ans = check(j)
      ans2 = check(k)
      if ans == true and ans2 == true then
        sum += (j + k)
      end    

    end
  end
  return sum
end        

a = abundant()
puts a

What this does is save every result (whether a number is a prime or not) in a Hashtable, and before making the calculation, it first checks if the result is already in the Hashtable of saved numbers. That is what caching means.

If you read your code, you'll see that you calculate whether each number is a prime 28124(!) times (once for each iteration in the inner loop, plus one when j==k), this many times, and for a heavy calculation as well... the fact that you re-calculate each number for so many times makes you code a few orders of magnitude slower than when caching the results.

Why does this code take 8 minutes to finish?

Some simple optimizations to prime finding:

Start by pushing 2 onto your primes list, and start by checking if 3 is a prime. (This eliminates needing to write special case code for the numbers 0 to 2)
You only have to check numbers that are odd for prime candidacy. (Or, if you start by adding 2/3/5 and checking 7, you only need to check numbers that are 1 or 5 after doing % 6. Or... You get the idea)
You only have to see if your current candidate x is divisible by factors up to sqrt(x)—because any factor above sqrt(x) divides x into a number below sqrt(x), and you've already checked all of those.
You only have to check numbers in your prime list, instead of all numbers, for divisors of x - since all composite numbers are divisible by primes. For example, 81 is 9*9 - but 9*9 is 3*3*9, 9 being composite, so you'll discover it's a prime when you check it against 3. Therefore you never need to test if 9 is a factor, and so on for every composite factor.

There are very optimized, sped up prime finding functions (see the Sieve of Atkin for a start), but these are the common optimizations that are easy to come up with.

Trying to find largest prime factor

So it looks like, as you have suggested, the issue is the recursion logic.

Just because you call a function recursively doesn't mean that the "parent" stops working - he just sits and waits for the "child" to finish, and then keeps going. This is where this "over looping" is happening. The code is actually not over looping but rather, finishing up.

You can see this in your puts statement. Notice, after the loop stops, sqrt increases because script now running the parent code, not the after the recursive piece (child) finishes.

For the fix, I did 2 things:
1. Create a Boolean that indicates that the code block has gone through recursion. If so, run this code, else... run something else.
2. If candidate is not 2, then increment by 2. This skips testing all even numbers except for 2. There is no need to test for other even numbers since it's not a prime.

def largest_prime_factor(num,prime_factors,recursive)
  candidate = 2
  until candidate >= Math.sqrt(num)
    recursive = false
    if num % candidate == 0
      num = num / candidate
      recursive = true
      prime_factors << candidate
      largest_prime_factor(num,prime_factors,recursive)
    end
    break if recursive
    candidate == 2 ? candidate += 1 : candidate += 2
  end
  prime_factors << num unless recursive
  prime_factors.last
end

Ruby: #8 on Project Euler, solution doesn't seem to work, but I feel so close

I think you should try to use the String methods in Ruby a bit more. Please take a look at this page here.

You would reach the same results with the much simpler code here:

sequence = "73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450"

## This will remove all \n
seq = sequence.tr("\n","")

def multiply_arr(a)
  prod = 1
  a.each do |f|
    prod = prod * f.to_i    
  end
  prod
end

def max_product(s,n)
  max = -1
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    max = (prod > max) ? prod : max 
  end
  max
end

puts max_product(seq,4)
puts max_product(seq,13)

I ran it here and got the following output

5832
23514624000

As you may see, the first product is the same you got. Haven't verified the second, but this is easy for you to do.

By the way, this kind of code is much more general, indeed. Now you may write things like

puts max_product(seq,5)

and receive

as an answer. Then you solved a much more general problem than 'calculate it for 4' and then 'calculate it for 13'.

By the way! If you want to know what sequence generate this max, you may easily rewrite your code to

def max_product(s,n)
  max = -1
  maxarr = []
  lim = s.length - n
  (0..lim).each do |pos|
    ns = s.slice(pos,n)
    arr = ns.each_char.to_a
    prod = multiply_arr(arr)
    if (prod > max) 
      max = prod
      maxarr = arr
    end
  end
  { "array" => maxarr, "prod" => max }
end

then you would get this

{"array"=>["9", "9", "8", "9"], "prod"=>5832}
{"array"=>["5", "5", "7", "6", "6", "8", "9", "6", "6", "4", "8", "9", "5"], "prod"=>23514624000}

Hope it helps!

Finding the largest prime factor of 600851475143

There's a couple problems with your solution. First of all, you never test that i is prime, so you're only finding the largest factor of the big number, not the largest prime factor. There's a Ruby library you can use, just require 'prime', and you can add an && i.prime? to your condition.

That'll fix inaccuracy in your program, but it'll still be slow and expensive (in fact, it'll now be even more expensive). One obvious thing you can do is just set result = i rather than doing result.push i since you ultimately only care about the last viable i you find, there's no reason to maintain a list of all the prime factors.

Even then, however, it's still very slow. The correct program should complete almost instantly. The key is to shrink the number you're testing up to, each time you find a prime factor. If you've found a prime factor p of your big number, then you don't need to test all the way up to the big number anymore. Your "new" big number that you want to test up to is what's left after dividing p out from the big number as many times as possible:

big_number = big_number/p**n

where n is the largest integer such that the right hand side is still a whole number. In practice, you don't need to explicitly find this n, just keep dividing by p until you stop getting a whole number.

Finally, as a SPOILER I'm including a solution below, but you can choose to ignore it if you still want to figure it out yourself.

require 'prime'

max = 600851475143; test = 3

while (max >= test) do
  if (test.prime? && (max % test == 0))
    best = test
    max = max / test
  else
    test = test + 2
  end
end

puts "Here's your number: #{best}"

Exercise: Prove that test.prime? can be eliminated from the if condition. [Hint: what can you say about the smallest (non-1) divisor of any number?]

Exercise: This algorithm is slow if we instead use max = 600851475145. How can it be improved to be fast for either value of max? [Hint: Find the prime factorization of 600851475145 by hand; it's easy to do and it'll make it clear why the current algorithm is slow for this number]

Project Euler #3 in Java; program not outputting result

You are wasting time calculating all the primes when you don't have too.

When you find the first prime, try reducing max by that prime until it is not longer divisible.
Then continue finding the next prime.
and reducing max by factoring out that prime.
each time check to see if max is equal to the current prime. If so, you are done.

Assuming you are finding primes correctly (which I believe you are) consider the following:

primes = 2,3,5,7,11,13
max = 99

is 99 divisible by 2 - no, try next prime.
is 99 divisible y  3 -  yes
max = 33
is 33 divisble by 3  - yes 
max = 11
is 11 divisible by 3 - no
by 5 - no
by 7 - no
by 11 - hey, max is a prime! And it must be the largest because
it can't be reduced anymore.

And if you want, when finding each prime factor of max, save it in a list.

Then multiply all the values in the list to see if the product == max.

Here is your code

import java.util.ArrayList;

public class Test {
    public static void main(String[] args){
        long max = 600851475143L;
          // right here, reduce max by current prime (which starts at 2)

        for (long i = 3; i <= max; i += 2){
            boolean prime = true;
            for (long j = 3; j < Math.sqrt(i); j++){
                if (i % j == 0){
                    prime = false;
                    break;
                }
            }
            if (prime)  {
            // right here, reduce max by current prime

            }
        }
    }
}

Project Euler Question 3 Help

For starters, instead of beginning your search at n / 2, start it at the square root of n. You'll get half of the factors, the other half being their complement.

eg:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.