Comments on twcrone/euler/problem3/largest_prime_factor.exs

largest_prime_factor.exs

ExUnit.start

defmodule LargestPrimeFactor do
  use ExUnit.Case, async: true

  @moduledoc """

  Project Euler
  
  Largest prime factor
  Problem 3

  The prime factors of 13195 are 5, 7, 13 and 29.

  What is the largest prime factor of the number 600851475143 ?
  
  https://projecteuler.net/problem=3

  ## Example

    iex> LargestPrimeFactor.calculate_for(13195)
    29

  """

  @doc """
  Calculates the largest prime factor for a number.
  """
  def calculate_for(num) do
    get_largest_prime_factor(num, 2)
  end

  defp get_largest_prime_factor(num, divisor) do
    if is_factor_of?(divisor, num) do
      next_candidate = Kernel.div(num, divisor)
      if is_prime?(next_candidate) do
        next_candidate
      else
        get_largest_prime_factor(num, divisor + 1)
      end
    else
    get_largest_prime_factor(num, divisor + 1)
    end
  end

  defp is_factor_of?(factor, num) do
  	Kernel.rem(num, factor) == 0
  end

  defp is_prime_factor_of?(factor, num) do
  	if is_prime?(factor) do
  		is_factor_of?(factor, num)
  	else
  		false
  	end
  end

  defp is_prime?(num) do
    is_prime?(num, 2)
  end

  defp is_prime?(num, factor) do
  	cond do
  	  num == 2 -> true
      is_factor_of?(factor, num) -> false
	    factor < (num/factor) -> is_prime?(num, factor + 1)
	    true -> true
    end
  end  

  # Tests

  test "get largest prime factor for 600851475143" do
  	answer = calculate_for(600851475143)
  	IO.puts "Answer is #{answer}"
  	assert answer > 0
  end

  test "get largest prime factor" do
  	assert is_prime?(29)
  	assert is_factor_of?(29, 13195)
  	assert is_prime_factor_of?(29, 13195)
  	assert calculate_for(13195) == 29
  end

  test "is a factor" do
    assert is_factor_of?(2, 4)
  end

  test "is not a factor" do
    assert is_factor_of?(3, 4) == false
  end

  test "is prime base case" do
  	assert is_prime?(2)
  end

  test "is prime" do
  	assert is_prime?(5)
  end

  test "is not prime" do
  	assert is_prime?(4) == false
  end

  test "is not prime more in depth" do
  	assert is_prime?(121) == false
  end

end

No real comments on the overall algorithm, I'm sure there are lots of ways to speed up the prime checking if you'd wanted to do it, but I know "develop a perfectly-optimized prime checking algorithm" wasn't the real goal of the problem.

I like the use of recursion

Line 4: Pretty sure async: true is default, so that parts probably not necessary here.

Lines 35 & 47: Kernel is imported by default, so you can refer to these functions without needing to specify the Kernel module. This is a bit of a stylistic thing though, I love imports, I know some people who hate it.

Lines 51-56: Equivalent to is_prime?(factor) && is_factor_of?(factor, num). I'm sure you would have caught that with another look through, we've all written code like that before :)

You could add one additional is_prime? function def (it would have to go above the one on line 58) with a guard clause like:
def is_prime?(num) when rem(num, 2) == 0, do: false
to skip doing the is_prime?(num, factor) -> is_factor_of?(factor, num) -> Kernel.rem(num, factor) == 0 search on any even numbers.

Yeah, didn't know && exists for Elixir. I meant to change my cond to pattern matching functions.

Cool. Thanks!

Yeah, kinda brute forced solution but even at that faster than Ruby or Groovy without much extra code.

Two things I suggest you look into... pattern matching and list comprehension. That will shorten/simplify your code a bit.

An example of using default values and matching:

  defp is_prime?(num, factor \\ 2)
  defp is_prime?(2, _), do: true
  defp is_prime?(num, factor) when factor * factor > num, do: true
  defp is_prime?(num, factor), do: !is_factor_of?(factor, num) && is_prime?(num, factor + 1)

The guard for num == 2 only saves you a multiplication, so I would just drop it, anyway.

You could also simplify this function all the way to boolean logic, but I think it's less readable...

  defp is_prime?(num, factor \\ 2) do 
    factor * factor > num || (!is_factor_of?(factor, num) && is_prime?(num, factor + 1))
  end

Cool, thanks! My learning is slow and is interrupted by work etc.