Как уменьшить повторное использование оператора % для более быстрого выполнения в C

Просто измените порядок индексации и рассчитайте A на основе ограничений:

void findAllSpecial(int N, void (*f)(int A, int B, int C))
{
    // 1 ≤ A,B,C ≤ N 
    for (int C = 1; C < N; ++C) {
        // B mod C = 0 
        for (int B = C; B < N; B += C) {
            // A mod B = C
            for (int A = C; A < N; A += B) {
                f(A, B, C);
            }
        }
    }
}

Без деления не бесполезно if только для циклов и операций сложения.

Во-первых, ваш код имеет неопределенное поведение из-за деления на ноль: когда k равно нулю, тогда j%k не определено, поэтому я предполагаю, что все ваши циклы должны начинаться с 1, а не 0.

Обычно операторы % и / выполняются намного медленнее, чем любая другая операция. Можно избавиться от большинства вызовов операторов % в вашем коде, выполнив несколько простых шагов.

Во-первых, посмотрите на строку if:

if (i % j == k && j%k == 0)

i % j == k имеет очень строгое ограничение по сравнению с k, что играет вам на руку. Это означает, что перебирать k вообще бессмысленно, так как есть только одно значение k, удовлетворяющее этому условию.

for (i = 1; i<=1000000 ; i++ ) {
      for ( j = 1; j<= 1000000; j++ ) {
         k = i % j;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

Чтобы избавиться от "i % j", переключите цикл. Это изменение возможно, так как на этот код влияет только то, какие комбинации i,j проверяются, а не в том порядке, в котором они вводятся.

for ( j = 1; j<= 1000000; j++ ) {
      for (i = 1; i<=1000000 ; i++ ) {
         k = i % j;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

Здесь легко наблюдать за тем, как ведет себя k, и использовать это для итерации k напрямую без итерации i и, таким образом, избавления от i%j. k выполняет итерацию от 1 до j-1, а затем делает это снова и снова. Итак, все, что нам нужно сделать, это перебрать k непосредственно в цикле i. Обратите внимание, что i%j вместо j == 1 всегда равно 0, а поскольку k==0 не удовлетворяет условию if, мы можем безопасно начать с j=2, пропустив <3390999>2103324

for ( j = 2; j<= 1000000; j++ ) {
      for (i = 1, k=1; i<=1000000 ; i++, k++ ) {
         if (k == j)
            k = 0;
         // Constrain k to the range of the original loop.
         if (k <= 1000000 && k > 0 && j%k == 0)
                  count++;
      }
}

По-прежнему бесполезно повторно запускать j%k для одних и тех же значений j,k (помните, что k повторяется несколько раз во внутреннем цикле). Например, для j=3 значения i и k идут {1,1}, {2,2}, {3,0}, {4,1}, {5,2},{6,0},... {n*3, 0}, {n*3+1, 1}, {n*3+2, 2},... (для любого значения n в диапазоне 0 < n <= (1000000-2)/3).

Значения за пределами n= floor((1000000-2)/3)== 333332 сложны — давайте посмотрим. Для этого значения n, i=333332*3=999996 и k=0, поэтому последняя итерация {i,k}: {n*3,0},{n*3+1,1},{n*3+2, 2} становится {999996, 0}, {999997, 1}, {999998, 2}. Вам действительно не нужно перебирать все эти значения n, так как каждое из них делает одно и то же. Все, что вам нужно сделать, это запустить его только один раз и умножить на количество допустимых значений n (в данном случае это 999996+1 — добавление 1 для включения n=0).

Поскольку это не охватывает все элементы, необходимо продолжить остальные значения: {999999, 0}, {1000000, 1}. Обратите внимание, что в отличие от других итераций здесь нет третьего значения, так как оно установило бы i вне допустимого диапазона.

for (int j = 2; j<= 1000000; j++ ) {
      if (j % 1000 == 0) std::cout << std::setprecision(2) << (double)j*100/1000000 << "%  \r" << std::flush;
      int innerCount = 0;
      for (int k=1; k<j ; k++ ) {
         if (j%k == 0)
             innerCount++;
      }
      int innerLoopRepeats = 1000000/j;
      count += innerCount * innerLoopRepeats;
      // complete the remainder:
      for (int k=1, i= j * innerLoopRepeats+1; i <= 1000000 ; k++, i++ ) {
         if (j%k == 0)
             count++;
      }

}

Это по-прежнему очень медленно, но, по крайней мере, выполняется менее чем за день. Можно получить дальнейшее ускорение, используя важное свойство делимости. Рассмотрим первый внутренний цикл (это почти то же самое для второго внутреннего цикла), и обратите внимание, что он выполняет много избыточной работы и делает это дорого. А именно, если j%k==0, это означает, что k делит j и существует пара K такая, что pairK*k==j. Пара k вычисляется тривиально:pairK=j/k.

Очевидно, что для k > sqrt(j) существует пара K < sqrt(j). Это означает, что любое k > sqrt(j) может быть извлечено просто путем сканирования всех k < sqrt(j). Эта функция позволяет вам перебрать только квадратный корень из всех интересных значений k. Поиск только значений sqrt(j) дает огромный прирост производительности, и вся программа может завершиться за считанные секунды.

Вот вид второго внутреннего цикла:

      // complete the remainder:
      for (int k=1, i= j * innerLoopRepeats+1; i <= 1000000 && k*k <= j; k++, i++ ) {
         if (j%k == 0)
         {
             count++;
             int pairI = j * innerLoopRepeats + j / k;
             if (pairI != i && pairI <= 1000000) {
                    count++;
             }
         }
      }

Первый внутренний цикл должен пройти аналогичное преобразование.

Ниже приведена очевидная оптимизация: Третий цикл с «k» действительно не нужен, так как уже есть отображение «многие в один» из (I, j) -> k

Из кода я понял, что вы хотите вычислить количество пар (i,j) так, что (i%j) является коэффициентом j. Это правильно или я что-то упустил?

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

for(i = 0; i<=1000000 ; i++ ) 
     for( j = 0; j<= 1000000; j++ ) 
     {
          a = i%j;
          for( k = 0; k <= j; k++ )   
             if (a == k && j%k == 0) 
                  count++;
      }

Мы поместили a = i%j во второй цикл, потому что нет необходимости вычислять его каждый раз при изменении k, так как он независим от k и для условия j%k == 0, чтобы быть правдой, k должно быть <= j, следовательно, измените ограничения цикла