Имеется код
int func(int a, int b) {
do {
a /= b;
} while (a % b == 0);
return a;
}
int main(){
...
for (int j=k; j <= n; j+=k){
s += func(j, k);
}
...
}
Программа ищет сумму чисел [1..n], 1 < n < 1 000 000 000. Причем, числа которые делятся на k должны быть заменены на "наименьший" делитель, например, 6 при k = 3 надо заменить на 2; 9 меняем на 1, т.к. 9 / 3 = 3 и 3 / 3 =1.
Возможно ли оптимизировать время выполнения данного участка кода. При n = 1000000000, k = 2, например, время выполнения > 1 сек, а ограничение 1 сек.
a/b
, даже еслиa
наb
не делится?...)openmp
это вообще просто сделать. Главное помнить, что подобная оптимизация может дать неожиданные результаты (выполнение может даже замедлиться из-за синхронизаций и т.п.)