Нахождение наименьшего общего кратного числа 1-20, получение неправильного ответа - PullRequest
Новая
       29

Нахождение наименьшего общего кратного числа 1-20, получение неправильного ответа

1 голос
/ 13 апреля 2019

Я пытаюсь решить проблему Project Euler # 5, «Какое наименьшее положительное число равномерно делится на все числа от 1 до 20?»

Для решения этой проблемы я создал методы поиска LCM (наименьшего общего кратного) с использованием GCD (наибольший общий делитель)
Используя метод LCM, я нахожу LCM первого и второго простого числа, затем использую результат этого метода, чтобы найти LCM результата и третьего простого числа, и т. Д., И т. Д. 

    static void Main(string[] args)
    {
        int listLength = 20;
        Boolean[] listOfNumbers = new Boolean[listLength];
        ArrayList listOfPrimes = new ArrayList();

        for (int iii = 0; iii < listLength; iii++)
        {
            listOfNumbers[iii] = true;
        }

        for (int iii = 2; iii < listLength; iii++)
        {
            if (listOfNumbers[iii])
            {
                for (int jjj = iii * 2; jjj < listLength; jjj = jjj + iii)
                {
                    listOfNumbers[jjj] = false;
                }
                listOfPrimes.Add(iii);
            }
        }

        int lcm = 1;
        for (int iii = 0; iii < listOfPrimes.Count; iii++)
        {
            lcm = LCM(lcm, (int)listOfPrimes[iii]);
        }

    }

    static public int GCD(int a, int b)
    {
        int division;
        int modulus;
        if (a < b)
        {
            int c = b;
            b = a;
            a = c;
        }
        division = a / b;
        modulus = a % b;
        if (modulus == 0)
        {
            return b;
        } else
        {
            return GCD(division, modulus);
        }
    }

    static public int LCM(int a, int b)
    {
        int lcm = (a * b) / GCD(a, b);
        return lcm;
    }

Реальный ответ должен быть 232792560, но я получаю 22044 при использовании только простых чисел для LCM и 51731680 при использовании всех 20 чисел для LCM
Очевидно, что ни один из ответов не был правильным, мне просто интересно, я на правильном пути или я что-то напутал? Если возможно, просто смотрите в правильном направлении

1 Ответ

1 голос
/ 13 апреля 2019

Это не просто простые числа, а их факторизации.Подумайте: что такое LCM 2, 3, 4?Если вы просто используете простые числа, вы получите 2 * 3 = 6, что явно не кратно 4. То, что вы хотите, это LCM 2, 3, 2 * 2. Как только вы разбили три числа таким образом, выможно игнорировать 2, потому что это, очевидно, коэффициент 2 * 2.

Чтобы расширить это:

  • LCM (2, 3, 4, 5) = LCM (2, 3,2 * 2, 5) = LCM (3, 2 * 2, 5) = 60
  • LCM (2, 3, 4, 5, 6) = LCM (2, 3, 2 * 2, 5,2 * 3) = LCM (3, 2 * 2, 5) = 60

Поскольку вы только что попросили тыкать в правильном направлении, я оставляю кодирование этого на ваше усмотрение.:)

...