Проверка совершенных способностей

Question

Совершенная сила - это число N, где A ^ B = N (A> = 1, B> ​​= 2)

Это мой код.Я пытаюсь найти, сколько из этих чисел существует между 1 и выбранным верхним пределом.

    static void Main(string[] args)
    {
        int PPwr_Count = 1; //number 1 is included by default.
        int Top_Limit = 1000000; //Can be any number up to 10^9
        for (int Number = 2; Number <= Top_Limit; Number++)
        {
            int myLog = (int)Math.Floor(Math.Log(Number, 2) + 1);
            for (int i = 2; i <= myLog; i++) 
            {
                //As a Math rule I only need to check below Base 2 Log of number
                int x = Convert.ToInt32(Math.Pow(Number, 1.0 / i));
                 if (Number == Math.Pow(x, i))
                 {
                     PPwr_Count++;
                     break;
                 }
                 else continue;
            }
        }
     } 

В настоящее время это работает.К сожалению, он становится довольно медленным после примерно 1000000 проверок.Как улучшить скорость этого алгоритма?

Answer 1

Math.Log стоит дорого, Math.Pow стоит дорого, двойники стоят дорого. Вы знаете, что не дорого? Умножение целых чисел.

Немного теории крафтинга: если A ^ B == n и n <10 ^ 9 и B> = 2, то max A близко к 5 * 10 ^ 4. Итак, давайте иметь набор совершенных способностей. Повторяйте от 2, пока i * i <= max_n, если i не задан, добавьте i * i, i * i * i и т. Д., Пока его значение меньше max_n. Если A = C ^ D, то A ^ B = C ^ (B * D) и уже установлено. </p>

static void Main(string[] args)
    {
        int PPwr_Count = 1; //number 1 is included by default.
        int Top_Limit = 1000000000; //Can be any number up to 10^9
        HashSet<int> hs = new HashSet<int>();

        for (int A = 2; A * A <= Top_Limit; ++A)
        {
            if (!hs.Contains(A))
            {
                //We use long because of possible overflow
                long t = A*A;
                while (t <= Top_Limit)
                {
                    hs.Add((int)t);
                    t *= A;
                    PPwr_Count++;
                }
            }
        }
        Console.WriteLine(PPwr_Count);
    }

РЕДАКТИРОВАТЬ: Это работает менее половины секунды при отладке на моем ноутбуке.

Answer 2

Переместить Math.Log(Number, 2) + 1 из цикла for.

int myLog = (int)Math.Floor(Math.Log(Number, 2) + 1);
for (int i = 2; i <= myLog; i++) 

Answer 3

Было бы проще искать в пространстве A и B, а не N. A из [2, ..., sqrt (N)], B из [Список простых чисел].

Answer 4

Я был бы склонен использовать совершенно другой подход.

Сначала создайте итератор, который перечисляет все простые числа вплоть до квадратного корня максимального размера.Итак, 2, 3, 5, 7, 11 ...

ОБНОВЛЕНИЕ: НИКАКОГО НЕ ЖДИТЕ, ЧТО НЕ РАБОТАЕТ.Это, например, не дает 36 в качестве идеальной степени.

Позвольте мне пересмотреть.

Создайте итератор, который перечисляет все числа от 2 до квадратного корня максимального размера.

Затем создайте итератор, который перечисляет все совершенные полномочия определенного данного числа вплоть до максимального размера.Это 2 ² , 2 ³ , 2 ⁴ , ...

Теперь объедините два итератора с запросом select-many, так что вы генерируете: 2 ² , 2 ³ , 2 ⁴ , ... 3 ² , 3 ³ , 3 ⁴ , ..., 4 ² , 4 ³ , 4 ⁴ , ...

Создайте хеш-набор из полученного запроса, чтобы сформировать объединение всех совершенных степеней, меньших, чем максимальный размер всех чисел, вплоть до квадратного корня из максимального размера.

Размер результирующего набора хэшей - это число, которое вы ищете.

Answer 5

Я бы попробовал работать с алгоритмом в другом направлении.

Начните с a = 2 и b = 2 и просматривайте каждый b, пока a ^ b> max_limit

Хитрость этого метода заключается в проверке только значений a, которые являются простыми числами

Хитрость в этом методе не в том, чтобы проверить значения a, которые являются совершенными степенями (например, не проверять 4, 8, 9 и т. Д.)

Answer 6

Другой вариант - вместо того, чтобы перебирать все числа и проверять, являются ли они степенями, вы можете сделать наоборот: генерировать все совершенные полномочия.

Так что, если вы начнете с базы 2, рассчитайте 2^1, 2^2 и т. Д. Затем вычислите 3^1, 3^2, 3^3 и т. Д. И т. Д.Вы также, вероятно, захотите сохранить каждый результат в HashSet, чтобы исключить двойные значения.В конце концов, подсчет так же прост, как hash.Count

Я не уверен, как производительность этого кода зависит от вашего кода (это определенно менее эффективно с точки зрения места), но это может работать и под другим углом.