Найти факторы

Question

Ну, я делаю программу на С ++, и мне нужно найти числа с общими факторами из массива. Я уже делаю это наивным образом.

int commonFactors(int p, int q){ 
    int count = 0; 

    if(q > p){ 
     for(int i = 2;i < q;i++){ 
      if((q%i==0)&&(p%i==0)){ 
       count++; 
       break; 
      } 
     } 
    } 
    else if(p > q){ 
     for(int i = 2;i < p;i++){ 
      if((p%i==0)&&(q%i==0)){ 
       count++; 
       break; 
      } 
     } 
    } 
    else{ 
     count = 1; 
    } 

    return count; 
} 

Хорошо, тогда мои тайм-ауты кода для больших входов. Мой диапазон ввода от 1 до 1000000 для любого элемента массива. Есть ли подсказка о том, как его эффективно вычислить?

У меня есть идея проверить только основные факторы, но я беспокоюсь о диапазоне, в котором можно проверить.

Answer 1

Если единственный вопрос: «У этих двух есть общий коэффициент (кроме одного)», то одним из вариантов было бы просто вычислить их наибольший общий делитель и проверить, является ли он одним. НОД может быть вычислен достаточно эффективно (определенно быстрее, чем просто подсчет всего пути до вашего номера) с помощью Euclidean algorithm:

gcd(a, 0) = a 
gcd(a, b) = gcd(b, a % b) 

Answer 2

Вы можете сделать это более эффективно, запустив цикл for до «sqrt (p)» (или q, в зависимости от меньшего числа конечно). Это должно ускорить работу.

Answer 3

Рассмотрим два числа: 9240 и 16170. Каждое число может быть записано как произведение (нескольких) простых чисел:

9240 = 2*2*3*5*7*11 
16170 = 2*3*5*7*7*11 

Из приведенного выше примера, должно быть очевидно, что общее число возможно Общими факторами будут общий список номеров, которые вы можете создать с помощью этих операндов. В этом случае набор чисел 2, 3, 5 и 11 будет производить 15 всего комбинаций.

Так что ваш код может сделать следующие шаги (я не буду писать код C++ для вас, как вы должны быть в состоянии сделать это легко самостоятельно):

1. Split каждый номер в его простые множители с помощью Integer factorization
2. Найти полное подмножество этих простых чисел, которые присутствуют в каждом списке (не забывайте, что некоторые из них могут оказаться более чем один раз в обоих списках и должны учитываться как отдельные из них, то есть в два раза)
3. Найдите все возможные числа, которые вы можете создать, объединив данные множество простых чисел

В последней части этого вы можете увидеть Dynamic programming идеи о том, как улучшить свою работу значительно по сравнению с наивным подхода.

Answer 4

Первой математики: Say А и В двух положительных не нулевых целых числах, будет называть C = gcd (A, B) наибольший общий делитель A и B, тогда, если M делит оба A и B, M делится C.

Итак, если вы хотите узнать только, есть ли у A и B общие делители, вы просто нужно проверить, больше ли C больше 1, если вы хотите знать все общие делители (или их число), вам нужно найти все делители C.

Алгоритм Евклида для поиска GCD двух чисел основан на следующем свойстве: скажем B < A, A = P * Q + R - евклидово деление P на Q, тогда если R = 0, GCD (A, B) = B, иначе НОД (A, B) = НОД (B, R) (см wikipedia)

Теперь некоторый код:

/* Euclidian algorythm to find Greatest Common Divisor 
Constraint (not controled here) p>0 and q>0 */ 
int gcd(int p, int q) { 
    // ensures q < p 
    if (p < q) { 
     int temp = p; 
     p = q; 
     q = temp; 
    } 
    int r = p % q; 
    // if q divises q, gcd is q, else gcd(p, q) is gcq(q, r) 
    return (r == 0) ? q : gcd(q, r); 
} 

bool sharedivisors(int p, int q) { 
    int d = gcd(p, q); 
    return d > 1; 
} 

int divisors(int p, int q) { 
    int d = gcd(p, q); 
    if (d == 1) { 
     return 1; 
    } 
    int count = 0; 
    for(int i=2; i<d/2; i++) { 
     if(d % i == 0) { 
      int j = d/i; 
      if (j > i) count += 2; 
      else { 
       if (j == i) count += 1; 
       break; 
      } 
     } 
    } 
    return count + 2; // and 1 and d 
} 

Answer 5

Counting факторы от 2 до большего ввода является грубой силой и продолжается даже если один из входов большой. Число общих делителей можно получить из показателей их простой факторизации. Легче вычислить их наибольший общий делитель первый

gcd = gcd(p0, q0) 
/* .. */ 
int gcd(p0, q0) 
{ 
    while(q0) 
    { 
     int swp = q0; 
     q0 = p0 % q0; 
     p0 = swp; 
    } 
    return p0; 
} 

, а затем рассчитывать его делители

• в Naiv образом (как и в вопросе)
• , всегда разделив GCD найденными делителей

• по штрихом факторизация

  p0^x0 * p1^x1 * .. * pN^xN = gcd 
  count = (1+x0) * (1+x1) * .. * (1+xN) 
  

Первичная факторизация требует первичного списка до sqrt (gcd).