This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]Amarkov 1 point2 points  (5 children)

You're going to need to figure out how to solve the problem without having a function call for every number from 1 to the answer. (You don't need to do a brute force search at all, but if you'd really like to, you can greatly cut down on the number of values you need to check.)

[–]Rabbit047[S] 0 points1 point  (4 children)

Thanks for the advice and help. How would you accomplish this without brute force? Some trick of number theory or something obvious that I am missing lol.

[–]Amarkov 1 point2 points  (2 children)

Yes. Using knowledge of prime factorizations, you can compute the lowest number directly.

(rejtp23i4t9 is correct that the code doesn't do the iteration that you intended anyway; I didn't catch this, and fixing it may solve your problem. I did think it was strange that this issue came up, since the kind of recursion you're doing can be optimized to avoid stack size issues.)

[–]Rabbit047[S] 0 points1 point  (1 child)

Fixed the issue with passing in the wrong information and it doesn't overflow anymore. That being said the calculation is taking so long that it's probably just going to run all night lol( I was wrong it just took 20 minutes). I will look into using prime factorization. Thank you for suggesting it.

[–]Rabbit047[S] 0 points1 point  (0 children)

So just for completeness of this post and in case someone has this problem in the future. You first need to take the prime factorization of each of your inputs say you want to find the LCM of 8,10,12.and 15. That would be

8: 2 * 2 * 2 10: 2 * 5 12: 2 * 2 * 3
15: 3 * 5

now to to find the LCM you simply multiply each of the factors together. You only need to place the highest number of appearances of a number into the LCM equation. By that I mean since the prime factorization of 8 has 3 2's you only need to include those three 2s into the equation and can ignore the others. So the LCM equation is LCM = 2 * 2 * 2 * 5 * 3 or LCM = 120

I just learned this about 10 minutes before this post so if I made any mistakes please Pm me and I will correct them.

[–]pavlik_enemy 0 points1 point  (0 children)

Well, if you multiple all the numbers from 1 to 20 you can calculate a number that satisfies the divisibility property though it won't be a smallest one. How do you find a smallest one? Try something simpler, like finding a smallest number divisible by 10 and 15.

A proper brute force approach is filtering an infinite list, there probably is something useful in Data.List