Как можно увеличить быстродействие этого кода на C++

Question

Как можно увеличить быстродействие этого кода на C++

Рейтинг: 1Ответов: 2Опубликовано: 25.06.2023

Решал задачу на нахождение чисел с нечетным делителем, столкнулся с проблемой, она заключается в том, что не хватает времени, как можно ускорить этот код?

#include <iostream>
#include <cmath>

int main() {
    int left, right; // отрезок на котором нужно найти эти числа
    std::cin >> left >> right;

    int counter;
    int pos = 1;
    for (int i = left; i <= right; i++) {
        counter = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) counter++;
        }
        if (counter % 2 == 1) {
            std::cout << pos << " " << i << " " << counter << " " << sqrt(i) << '\n';
            pos++;
        }
        
    }

    return 0;
}

c#

Источник: Stack Overflow на русском

Answer 1

▲ 4

Зная что число с нечётным количеством делителей - полный квадрат (док.во) можно составить алгоритм:

#include <iostream>
#include <cmath>

int main() {
    int left, right; // отрезок на котором нужно найти эти числа
    std::cin >> left >> right;

    int l = ceil(sqrt(left));
    int r = floor(sqrt(right));

    for (int i = l; i <= r; i++) {
        std::cout << i * i << " " << i << '\n';
    }

    return 0;
}

Answer 2

▲ 0

В добавок могу посоветовать использовать в начале программы:

ios::sync_with_stdio(0); 
cin.tie(0); 
cout.tie(0);

Это ускорит работу cin и cout.

Как можно увеличить быстродействие этого кода на C++

Ответы