Checking whether a number contains numbers 1 to n as factors

Question

I am trying to solve Project Euler Challenge 5, What is the smallest possible number that is evenly divisible by all the numbers from 1 to 20.

My problem is that my isMultiple() method doesn't return true when it should.

* My Code *

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Challenge_5
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine(isMultiple(2520, 10)); //should return True
            Console.WriteLine(smallestMultiple(20)); //should return 232792560
            Console.ReadLine();
        }

        static int factorial(int n)
        {
            int product = 1;
            for (int i = 1; i <= n; i++)
            {
                product *= i;
            }

            return product; //returns the factorial of n, (n * n-1 * n-2... * 1)
        }

        static bool isMultiple(int number, int currentFactor)
        {
            bool returnBool = false;

            if (currentFactor == 1)
            {
                returnBool = true; // if all factors below largestFactor can divide into the number, returns true
            }
            else
            {
                if (number % currentFactor == 0)
                {
                    currentFactor--;
                    isMultiple(number, currentFactor);
                }
            }

            return returnBool;
        }

        static int smallestMultiple(int largestFactor)
        {
            for (int i = largestFactor; i < factorial(largestFactor); i+= largestFactor) //goes through all values from the kargestFactor to largestFactor factorial
            {
                if (isMultiple(i, largestFactor))
                {
                    return i; // if current number can be evenly divided by all factors, it gets returned
                }
            }

            return factorial(largestFactor); // if no numbers get returned, the factorial is the smallest multiple
        }
    }
}

I know there are much easier ways to solve this, but I want the program to be used to check the lowest multiple of the numbers from 1 to any number, not just 20.

Help would be much appreciated.

EDIT

Thanks to help, i have fixed my code by changing line 42 from

isMultiple(number, currentFactor);

to

returnBool = isMultiple(number, currentFactor);

I also fixed the problem with not getting an accurate return value for smallestMultiple(20);

by changing some of the variables to long instead of int

For some math, see [OEIS: A003418](https://oeis.org/A003418). — Jeppe Stig Nielsen, Oct 28 '18 at 18:45

score 2 · Accepted Answer · answered Oct 28 '18 at 19:57

2

Your problem is you forgot to use the output of isMultiple in your recursive part

if (number % currentFactor == 0)
{
    currentFactor--;
    returnBool = isMultiple(number, currentFactor); //you need a to save the value here.
}

Without assigning returnBool there is no way of knowing if the inner isMultiple returned true or not.

answered Oct 28 '18 at 19:57

Scott Chamberlain

124,994
33
282
431

Thanks for this, my program now identifies the correct output for isMultiple(2520, 10) – BenWornes Oct 28 '18 at 23:11

dx_over_dt · Answer 2 · 2019-12-30T00:10:38.290

Scott's answer is perfectly valid. Forgive me if I'm wrong, but it sounds like you're a student, so in the interest of education, I thought I'd give you some pointers for cleaning up your code.

When writing recursive functions, it's (in my opinion) usually cleaner to return the recursive call directly if possible, as well as returning base cases directly, rather than storing a value that you return at the end. (It's not always possible, in complicated cases where you have to make a recursive call, modify the return value, and then make another recursive call, but these are uncommon.)

This practice:

makes base cases very obvious increasing readability and forces you to consider all of your base cases
prevents you from forgetting to assign the return value, as you did in your original code
prevents potential bugs where you might accidentally do some erroneous additional processing that alters the result before you return it
reduces the number of nested if statements, increasing readability by reducing preceding whitespace
makes code-flow much more obvious increasing readability and ability to debug
usually results in tail-recursion which is the best for performance, nearly as performant as iterative code
- caveat: nowadays most compilers' optimizers will rejigger production code to produce tail-recursive functions, but getting into the habit of writing your code with tail-recursion in the first place is good practice, especially as interpreted scripting languages (e.g. JavaScript) are taking over the world, where code optimization is less possible by nature

The other change I'd make is to remove currentFactor--; and move the subtraction into the recursive call itself. It increases readability, reduces the chance of side effects, and, in the case where you don't use tail-recursion, prevents you from altering a value that you later expect to be unaltered. In general, if you can avoid altering values passed into a function (as opposed to a procedure/void), you should.

Also, in this particular case, making this change removes up to 3 assembly instructions and possibly an additional value on the stack depending on how the optimizer handles it. In long running loops with large depths, this can make a difference*.

static bool isMultiple(int number, int currentFactor)
{
    if (currentFactor == 1)
    {
        // if all factors below largestFactor can divide into the number, return true
        return true;
    }

    if (number % currentFactor != 0)
    {
        return false;
    }

    return isMultiple(number, currentFactor - 1);
}

* A personal anecdote regarding deep recursive calls and performance...

A while back, I was writing a program in C++ to enumerate the best moves for all possible Connect-4 games. The maximum depth of the recursive search function was 42 and each depth had up to 7 recursive calls. Initial versions of the code had an estimated running time of 2 million years, and that was using parallelism. Those 3 additional instructions can make a HUGE difference, both for sheer number of additional instructions and the amount L1 and L2 cache misses.

Thanks for this feedback, i only recently started using recursive functions and this helped a lot. — BenWornes, Oct 28 '18 at 23:25

Ashkan Mobayen Khiabani · Answer 3 · 2018-10-29T04:46:06.770

This algorithm came up to my mind right now, so please anyone correct me if i'm wrong.

As composite numbers are made by multiplication of prime numbers (and prime numbers can not be generated from multiplication of any other numbers) so the number must be multiplied to all prime numbers, some numbers like 6 when they are reached our smallest number is dividable (as its already multiplied to 2 and 3), but for those that are not, multiplying by a prime number (that is obviously less than the number itself so should be in our prime list) would make our smallest dividable to that number too. so for example when we get to 4, multiplying by2` (a prime number less than 4) would be enough, 8 and 9 the same way, ...

bool IsPrime(int x)
{
    if(x == 1) return false;
    for(int i=2;i<=Math.Sqrt(x);i+=2)
       if(x%i==0) return false;
       return true;
}

int smallest = 1;
List<int> primes = new List<int>();
for(int i=1;i<=20;i++)
   if(IsPrime(i)) 
   {
      smallest *= i;
      primes.Add(i);
   }    
   else if(smallest % i != 0)
       for(int j=0;j<primes.Count;j++)
            if((primes[j]*smallest)%i == 0)
            {
                 smallest *= primes[j];
                 break;
            }

Edit: As we have list of prime numbers so the best way to find out if a number is prime or not would be:

bool IsPrime(int x)
{
    if(x == 1) return false;
    for(int i = 0; i< primes.Count; i++)
        if(x%primes[i] == 0) return false;
    return true;
}

Checking whether a number contains numbers 1 to n as factors

3 Answers3