Сумма наибольшего общего делителя всех чисел до n с n

Я только что реализовал алгоритм GCD между двумя числами, что довольно легко, но я не могу понять, что вы пытаетесь сделать там.
Я читаю там, что вы пытаетесь подвести итог серии GCD; но GCD — это результат ряда математических операций между двумя или более числами, которые приводят к единственному значению.
Я не математик, но я думаю, что «сигма» в том виде, в котором вы ее написали, означает, что вы пытаетесь суммировать GCD чисел от 1 до 10.000.000; что не имеет смысла вообще, для меня.

Какие значения вы пытаетесь найти GCD? Все числа от 1 до 10.000.000? Я сомневаюсь, что это так.

В любом случае, вот очень простая (и поспешная) реализация алгоритма GCD Евклида:

int num1=0, num2=0;
cout << "Insert the first number: ";
cin >> num1;

cout << "\n\nInsert the second number: ";
cin >> num2;
cout << "\n\n";
fflush(stdin);

while ((num1 > 0) && (num2 > 0))
{
if ((num1 - num2) > 0)
{
//cout << "..case1\n";
num1 -= num2;
}
else if ((num2 - num1) > 0)
{
//cout << "..case2\n";
num2 -= num1;
}
else if (num1 = num2)
{
cout << ">>GCD = " << num1 << "\n\n";
break;
}
}

Хорошее место, чтобы начать смотреть на эту проблему Вот в онлайн-энциклопедии целочисленных последовательностей, поскольку вы пытаетесь вычислить сумму последовательности A018804 между 1 и N. Поскольку вы обнаружили подходы, которые пытаются использовать простую функцию Euclid GCD, слишком медленны, так что вам нужно Более эффективный способ расчета результата.

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

У меня был случай, чтобы изучить вычисления сумм GCD, потому что проблема возникла в учебнике HackerEarth под названием GCD Sum. Гуглинг появился немного научные статьи с полезными формулами, о которых я сообщаю здесь, так как они не упоминаются в Статья MathOverflow связанный девиантфаном.

Для взаимно простых m и n (то есть gcd (m, n) == 1) функция является мультипликативной:

gcd_sum[m * n] = gcd_sum[m] * gcd_sum[n]

Полномочия простых чисел p:

gcd_sum[p^e] = (e + 1) * p^e - e * p^(e - 1)

Если нужно вычислить только одну сумму, то эти формулы могут быть применены к результату факторизации рассматриваемого числа, что все равно будет намного быстрее, чем повторное gcd() звонки или прохождение Ригмароль, предложенный Толя.

Тем не менее, формулы можно так же легко использовать для эффективного вычисления целых таблиц функции. По сути, все, что вам нужно сделать, это подключить их к алгоритму линейное время вычисление Эйлера и все готово — это вычисляет все GCD суммирует до миллиона намного быстрее, чем вы можете вычислить единственную сумму GCD для числа 10 ^ 6 посредством вызовов gcd() функция. По сути, алгоритм эффективно перечисляет наименьшие факторные разложения чисел до n таким образом, что позволяет легко вычислить любую мультипликативную функцию — коэффициент Эйлера (a.k.a. phi), сигмы или, по сути, суммы GCD.

Вот немного кода гашиша, который вычисляет таблицу сумм GCD для небольших ограничений — «маленький» в том смысле, что sqrt (N) * N не переполняет 32-разрядное целое число со знаком. IOW, он работает для предела 10 ^ 6 (достаточно для задачи HackerEarth с пределом 5 * 10 ^ 5), но предел 10 ^ 7 потребует залипания (long) бросает в нескольких стратегических местах. Тем не менее, такое усиление функции для работы на более высоких диапазонах остается в качестве пресловутого упражнения для читателя … 😉

static int[] precompute_Pillai (int limit)
{
var small_primes = new List<ushort>();
var result = new int[1 + limit];

result[1] = 1;

int n = 2, small_prime_limit = (int)Math.Sqrt(limit);

for (int half = limit / 2; n <= half; ++n)
{
int f_n = result[n];

if (f_n == 0)
{
f_n = result[n] = 2 * n - 1;

if (n <= small_prime_limit)
{
small_primes.Add((ushort)n);
}
}

foreach (int prime in small_primes)
{
int nth_multiple = n * prime, e = 1, p = 1;  // 1e6 * 1e3 < INT_MAX

if (nth_multiple > limit)
break;

if (n % prime == 0)
{
if (n == prime)
{
f_n = 1;
e = 2;
p = prime;
}
else break;
}

for (int q; ; ++e, p = q)
{
result[nth_multiple] = f_n * ((e + 1) * (q = p * prime) - e * p);

if ((nth_multiple *= prime) > limit)
break;
}
}
}

for ( ; n <= limit; ++n)
if (result[n] == 0)
result[n] = 2 * n - 1;

return result;
}

Как и было обещано, это вычисляет все суммы GCD до 500 000 за 12,4 мс, тогда как единственная сумма для 500 000 вычисляется через gcd() вызовы занимают 48,1 мс на той же машине. Код был проверен по OEIS список функции Pillai (A018804) до 2000 года и до 500 000 против функции на основе gcd — на это ушло целых 4 часа.

Существует целый ряд оптимизаций, которые могут быть применены для того, чтобы сделать код значительно быстрее, например, заменить деление по модулю умножением (с обратным) и сравнением, или сократить еще несколько миллисекунд путем перехода к «первому чистому верхнему» ‘loop modulo 6. Однако я хотел показать алгоритм в его базовой неоптимизированной форме, потому что (а) он достаточно быстрый, как есть, и (б) он может быть полезен для других мультипликативных функций, а не только для сумм GCD.

P.S .: тестирование по модулю посредством умножения на обратное описано в разделе 9 статьи Granlund / Montgomery Деление по инвариантным целым числам с использованием умножения но трудно найти информацию об эффективном вычислении обратных степеней по модулю 2. В большинстве источников используется алгоритм расширенного Евклида или подобное избыточное убийство. Итак, вот функция, которая вычисляет мультипликативные обратные по модулю 2 ^ 32:

static uint ModularInverse (uint n)
{
uint x = 2 - n;

x *= 2 - x * n;
x *= 2 - x * n;
x *= 2 - x * n;
x *= 2 - x * n;

return x;
}

Это эффективно пять итераций Ньютон-Рафсона, на случай, если кому-то все равно. 😉

Вы можете использовать Seive для хранения наименьшего простого множителя из всех чисел, меньших чем 10 ^ 7
и по факторизации заданного числа вычислите ваш ответ напрямую ..