, чьи единственные простые множители составляют 2, 3 или 5, называются уродливыми числами.

Пример:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

1 можно рассматривать как 2 ^ 0.

Я работаю над поиском n-го уродливого номера. Обратите внимание, что эти числа чрезвычайно редко распределяются, так как n становится большим.

Я написал тривиальную программу, которая вычисляет, является ли данное число некрасивым или нет. Для n> 500 - это стало очень медленно. Я попытался использовать памятку - наблюдение: ugly_number * 2, ugly_number * 3, ugly_number * 5 все безобразно. Даже при том, что это медленно. Я попытался использовать некоторые свойства журнала - так как это уменьшит эту проблему от умножения до сложения - но пока не так много удачи. Мысль поделиться этим со всеми вами. Есть интересные идеи?

Используя концепцию, похожую на «Сито Эратосфена» (спасибо Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

я - это уродливое число.

Даже это довольно медленно. Я пытаюсь найти 1500-й уродливый номер.