Получение факторов числа

Question

Проблема: я пытаюсь изменить этот алгоритм, чтобы сделать его быстрее. Что будет первым рефакторингом здесь для скорости?

public int GetHowManyFactors(int numberToCheck)
    {
        // we know 1 is a factor and the numberToCheck
        int factorCount = 2; 
        // start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
        for (int i = 2; i < numberToCheck; i++) 
        {
            if (numberToCheck % i == 0)
                factorCount++;
        }
        return factorCount;
    }

Answer 1

Первая оптимизация, которую вы можете сделать, заключается в том, что вам нужно проверить только квадратный корень из числа.Это происходит потому, что факторы встречаются парами, где один меньше квадратного корня, а другой больше.

Единственное исключение из этого правила: если n является точным квадратом, то его квадратный корень является фактором n но не является частью пары.

Например, если ваш номер 30, коэффициенты в этих парах:

• 1 x 30
• 2 x 15
• 3 x 10
• 5 x 6

Таким образом, вам не нужно проверять числа больше 5, потому что все остальные факторы уже могут быть выведены для существованиякак только вы найдете соответствующий маленький фактор в паре.

Вот один из способов сделать это в C #:

public int GetFactorCount(int numberToCheck)
{
    int factorCount = 0;
    int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck));

    // Start from 1 as we want our method to also work when numberToCheck is 0 or 1.
    for (int i = 1; i < sqrt; i++)
    {
        if (numberToCheck % i == 0)
        {
            factorCount += 2; //  We found a pair of factors.
        }
    }

    // Check if our number is an exact square.
    if (sqrt * sqrt == numberToCheck)
    {
        factorCount++;
    }

    return factorCount;
}

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

Answer 2

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

Answer 3

Первое, на что нужно обратить внимание, - это нахождение всех основных факторов.Получив эти данные, легко найти количество полных делителей: для каждого простого числа прибавьте 1 к числу появлений и умножьте их вместе.Таким образом, для 12 = 2 * 2 * 3 у вас есть (2 + 1) * (1 + 1) = 3 * 2 = 6 факторов.

Из первого следует следующее: когда вы найдете фактор,разделите его так, чтобы полученное число было меньше.Когда вы комбинируете это с фактом, что вам нужно только проверить квадратный корень текущего числа, это огромное улучшение.Например, рассмотрите N = 10714293844487412. Наивно это сделало бы N шагов.Проверка до его квадратного корня занимает sqrt (N) или около 100 миллионов шагов.Но так как факторы 2, 2, 3 и 953 обнаружены на ранней стадии, вам нужно проверить только один миллион - улучшение в 100 раз!

Еще одно улучшение: вам не нужно проверять каждое число, чтобыпосмотрите, делит ли он ваше число, только простые числа.Если вам удобнее, вы можете использовать 2 и нечетные числа, или 2, 3, и числа 6n-1 и 6n + 1 (базовое сито для колес).

Вот еще одно приятное улучшение.Если вы можете быстро определить, является ли число простым, вы можете еще больше сократить потребность в делении.Предположим, что после удаления небольших факторов у вас есть 120528291333090808192969. Даже проверка его квадратного корня займет много времени - 300 миллиардов шагов.Но тест Миллера-Рабина (очень быстрый - возможно, от 10 до 20 наносекунд ) покажет, что это число является составным.Как это помогает?Это означает, что если вы проверите его корень куба и не найдете факторов, то останется ровно два простых числа.Если число является квадратом, его факторы простые;если число не является квадратом, числа являются различными простыми числами.Это означает, что вы можете умножить свой «промежуточный итог» на 3 или 4 соответственно, чтобы получить окончательный ответ - даже не зная факторов!Это может иметь большее значение, чем вы думаете: количество необходимых шагов упало с 300 миллиардов до всего лишь 50 миллионов, улучшение в 6000 раз!

Единственная проблема с вышесказанным - Миллер-Рабинможно только доказать, что числа составные;если ему дано простое число, оно не может доказать, что число простое.В этом случае вы, возможно, захотите написать функцию доказательства простоты, чтобы избавить себя от усилий по разложению до квадратного корня из числа.(В качестве альтернативы, вы могли бы просто сделать еще несколько тестов Миллера-Рабина, если бы вы были уверены с высокой уверенностью, что ваш ответ верен, а не является доказательством того, что это так. Если число проходит 15 тестов, то оно составное с вероятностью менее 1в миллиард.)

Answer 4

Похоже, что здесь обсуждается именно эта тема: Алгоритм вычисления числа делителей заданного числа

Надеюсь, это поможет

Answer 5

1. Вы можете ограничить верхний предел вашего цикла FOR до NumberToCheck / 2

2. Запустите свой счетчик цикла с 2 (если ваше число четное) или с 3 (для нечетных значений). Это должно позволить вам проверять каждое другое число, сбрасывая количество циклов еще на 50%.

   public int GetHowManyFactors(int numberToCheck)
   {
     // we know 1 is a factor and the numberToCheck
     int factorCount = 2; 
   
     int i = 2 + ( numberToCheck % 2 ); //start at 2 (or 3 if numberToCheck is odd)
   
     for( ; i < numberToCheck / 2; i+=2) 
     {
        if (numberToCheck % i == 0)
           factorCount++;
     }
     return factorCount;
   }
   

Answer 6

https://codility.com/demo/results/demoAAW2WH-MGF/

 public int solution(int n) {
      var counter = 0;          
      if (n == 1) return 1;
      counter = 2; //1 and itself      
      int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n)));
      for (int i = 2; i <= sqrtPoint; i++)
      {
        if (n % i == 0)
        {
          counter += 2; //  We found a pair of factors.         
        }       
      }
      // Check if our number is an exact square.
      if (sqrtPoint * sqrtPoint == n)
      {
        counter -=1;
      }

      return counter;
    }

Answer 7

Простой в реализации алгоритм, который приведет вас намного дальше, чем пробное деление, - Поллард Ро

Вот реализация Java, которую легко адаптировать к C #: http://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html

Answer 8

Что ж, если вы собираетесь много использовать эту функцию, вы можете использовать модифицированный алгоритм Эратосфена http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes и хранить ответы в интервале от 1 до Макс в массиве.Он будет запускать IntializeArray () один раз и после того, как вернет ответы в 0 (1).

const int Max =1000000;
int arr [] = new int [Max+1];

public void InitializeArray()
{
    for(int i=1;i<=Max;++i)
        arr[i]=1;//1 is factor for everyone

    for(int i=2;i<=Max;++i)
        for(int j=i;i<=Max;i+=j)
           ++arr[j];
}
public int GetHowManyFactors(int numberToCheck)
{
   return arr[numberToCheck];
}

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

---

Примечание. Я исправил свой код!