Самая большая оптимизация алгоритма Prime Factor

Question

Я пытаюсь улучшить этот интересный алгоритм настолько, насколько смогу.

Пока у меня есть это:

using System;

class Program
{

    static void Main()
    {
        ulong num, largest_pFact;
        uint i = 2;
        string strNum;

        Console.Write("Enter number: ");
        strNum = Console.ReadLine();
        num = ulong.Parse(strNum);
        largest_pFact = num;


        while (i < Math.Sqrt((double) largest_pFact))
        {
            if (i % 2 != 0 | i == 2) {
                if (largest_pFact % i == 0) 
                    largest_pFact /= i;
            }

            i++;
        }

        Console.WriteLine("Largest prime factor of {0} is: {1}", num, largest_pFact);
        Console.ReadLine();

    }
}

Так есть идеи?

Спасибо!

РЕДАКТИРОВАТЬ : Я реализовал алгоритм Бена, спасибо всем за вашу помощь!

Answer 1

У меня есть более быстрый алгоритм здесь .

Устраняет квадратный корень и правильно обрабатывает повторяющиеся факторы.

Оптимизация дополнительно:

static private ulong maxfactor (ulong n)
{
    unchecked
    {
        while (n > 3 && 0 == (n & 1)) n >>= 1;

        uint k = 3;
        ulong k2 = 9;
        ulong delta = 16;
        while (k2 <= n)
        {
            if (n % k == 0)
            {
                n /= k;
            }
            else
            {
                k += 2;
                if (k2 + delta < delta) return n;
                k2 += delta;
                delta += 8;
            }
        }
    }

    return n;
}

Вот рабочая демонстрация: http://ideone.com/SIcIL

Answer 2

Во-первых, вам не нужно запускать Math.Sqrt на каждой итерации.

    int root = Math.Sqrt((double) largest_pFact);

    while (i < root)
    {
        if ((i % 2 != 0 | i == 2) && largest_pFact % i == 0) {
            largest_pFact /= i;
            root = Math.Sqrt((double) largest_pFact);
        }

        i++;
    }

Answer 3

Ну, во-первых, я бы переместил особый случай 2 из цикла, нет смысла проверять это во всем цикле, когда он может быть обработан один раз. Если возможно, используйте тип данных int вместо uint, так как обычно он быстрее:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
while (i < Math.Sqrt((double) largest_pFact)) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

Расчет квадратного корня является относительно дорогим, поэтому его также следует сделать заранее:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (i % 2 != 0) {
    if (largest_pFact % i == 0) {
      largest_pFact /= i;
    }
  }
  i++;
}

Тогда я бы увеличил i с шагом в два, чтобы уменьшить одну проверку по модулю:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  if (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

Для работы, я считаю, что вам нужно while вместо if внутри цикла, в противном случае будут пропущены повторяющиеся факторы:

if (largest_pFact % 2 == 0) {
  largest_pFact /= 2;
}
int i = 3;
int sq = Math.Sqrt((double) largest_pFact);
while (i < sq) {
  while (largest_pFact % i == 0) {
    largest_pFact /= i;
  }
  i += 2;
}

Answer 4

-Store Math.Sqrt ((double) large_pFact) в некоторой переменной, предпочтительно ulong.Это позволяет избежать пересчета функции при каждом прохождении цикла, и целочисленное сравнение может быть быстрее, чем сравнение с плавающей точкой.Вам нужно будет изменить сравнение на <= if. </p>

- Избегать зацикливания на четных числах вообще.Просто включите специальный случай для i = 2, а затем начните с i в 3, увеличивая на 2 в каждом цикле.Вы можете пойти еще дальше, разрешив i = 2,3 быть особыми случаями, а затем протестировать только i = 6n + 1 или 6n-1.

Answer 5

Всегда быстрее искать между sqrt (num) и 2, чем начинать с num / 2. У каждой пары факторов (кроме квадратно-коренной) есть одно число, которое меньше sqrt (num).

Пример: для 15, int (sqrt (15)) == 3 15/3 = 5, поэтому вы нашли коэффициент «5», начав тестирование с 3 вместо 7.

Answer 6

Я думаю:

• генерирует простые числа до num / 2
• , затем проверяет от наибольшего к низшему, если ваш num делится на простое

будет быстрее.

edit num / 2 НЕ sqrt