Поиск факторов
Ну, я делаю программу на C ++, и мне нужно найти числа с общими факторами из массива. Я уже делаю это наивным способом.
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 для любого элемента в массиве. Любая подсказка о том, как рассчитать это эффективно?
У меня есть идея проверки только с основными факторами, но я беспокоюсь о диапазоне проверки.
Решение
Если единственным вопросом является «есть ли у этих двух общий фактор (кроме одного)», то одним из вариантов будет просто вычислить их наибольший общий делитель и проверить, равен ли он одному. GCD может быть вычислен довольно эффективно (определенно быстрее, чем просто считать все до ваших чисел), используя Евклидов алгоритм:
gcd(a, 0) = a
gcd(a, b) = gcd(b, a % b)
Другие решения
Вы можете сделать это более эффективно, запустив цикл for до «sqrt (p)» (или q, в зависимости от меньшего числа, конечно).
Это уже должно ускорить процесс.
Рассмотрим два числа: 9240 и 16170. Каждое число можно записать как произведение (нескольких) простых чисел:
9240 = 2*2*3*5*7*11
16170 = 2*3*5*7*7*11
Из приведенного выше примера должно быть очевидно, что общее количество возможный общими факторами будет общий список чисел, которые вы можете создать с помощью этих операндов. В этом случае набор чисел 2, 3, 5, а также 11 будет производить 15 Всего комбинаций.
Таким образом, ваш код может выполнять следующие шаги (я не собираюсь писать для вас код на C ++, поскольку вы сами сможете это сделать):
- Разделите каждое число на основные факторы, используя Целочисленная факторизация
- Найдите полное подмножество тех простых чисел, которые присутствуют в каждом списке (не забывайте, что некоторые из них могут появляться более одного раза в обоих списках и должны учитываться как отдельные, то есть дважды)
- Найдите все возможные числа, которые вы можете создать, комбинируя заданный набор простых чисел
Для последней части этого вы можете увидеть Динамическое программирование за идеи о том, как улучшить его производительность существенно по сравнению с наивно подход.
Сначала немного математики: скажем, A и B — два положительных, а не нулевых целых числа, назовем 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, иначе GCD (A, B) = GCD (B, R) (ref википедия)
Теперь немного кода:
/* 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
}
Подсчет коэффициентов от 2 до большего — это грубая сила и длится долго, даже если один из входов большой.
Число общих делителей можно получить из показателей их простой факторизации. Проще сначала вычислить их наибольший общий делитель
gcd = gcd( p0, q0 )
/* .. */
int gcd( p0, q0 )
{
while( q0 )
{
int swp = q0;
q0 = p0 % q0;
p0 = swp;
}
return p0;
}
а затем посчитать его делителей
- наивно (как в вопросе)
- всегда разделяя gcd с найденными делителями
-
путем простой факторизации
p0^x0 * p1^x1 * .. * pN^xN = gcd count = (1+x0) * (1+x1) * .. * (1+xN)
Простая факторизация требует простого списка до sqrt (gcd).
detector