Created
August 17, 2015 16:40
-
-
Save jordan0day/62045b8d4f2e10b52365 to your computer and use it in GitHub Desktop.
Comments on twcrone/euler/problem3/largest_prime_factor.exs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 |
Cool, thanks! My learning is slow and is interrupted by work etc.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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:
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...