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

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 х 30
• 2 х 15
• 3 х 10
• 5 х 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. Вы можете ограничить верхний предел вашего цикла 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 4

Похоже, есть длинная дискуссия о точной теме здесь: Algorithm to calculate the number of divisors of a given number

Надеется, что это помогает

Answer 5

Ну, если вы собираетесь использовать эту функцию много вы можете использовать модифицированную алгоритм Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes и сохранить answars для интервала от 1 до Max в массиве. Он будет запускать 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]; 
} 

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

---

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

Answer 6

Первое, что нужно заметить, это то, что достаточно найти все основные факторы. Как только у вас есть это, легко найти количество полных делителей: для каждого числа прибавьте 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 7

простой реализовать алгоритм, который приведет вас гораздо дальше, чем испытательный раздельном Pollard Rho

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

Answer 8

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; 
    }