Как я могу дополнительно сократить время выполнения этого кода
Как мне уменьшить время выполнения этого кода и довести его до 3 сек. А и В варьируются от 1 до 10 ^ 9 и тестовые случаи от 1 до 100
#include <iostream>
#include <cmath>
using namespace std;
static int testCases;
static int result[100];int main()
{
cin>>testCases;
for (int i = 0; i < testCases; i++) {
int a, b;
cin>>a;
cin>>b;
int count = 0;
while (a <= b) {
double lim = sqrt(a);
int special = 1;
for (int z = 2; z <= lim; z++) {
if (a % (z * z) == 0) {
special = 0;
break;
}
}
if (special == 1)
count++;
a++;
}
result[i]=count;
}
for (int i = 0; i < testCases; i++)
cout<<result[i]<<"\n";
}
Решение
Хотя этот вопрос больше подходит для http://codereview.stackexchange.com, вот один совет …
Изменить это:
while (a <= b)
{
double lim = sqrt(a);
...
a++;
}
К этому:
int lim = (int)sqrt(a);
int max = (lim+1)*(lim+1);
while (a <= b)
{
...
a++;
if (a == max)
{
lim++;
max = (lim+1)*(lim+1);
}
}
Помимо экономии времени, затрачиваемого на выполнение функции sqrtЕсли вы включите оптимизацию компилятора в настройках вашего проекта, то он может применить развертывание цикла во внешнем и / или внутреннем циклах, так как на данный момент в этих циклах нет других вызовов функций внутри этих циклов.
Другим советом было бы выполнить тест для z=2 а также z=3 отдельно, и с этого момента, тестировать только z=6N-1 а также z=6N+1 (Т.е. все числа, которые не являются кратными 2 или 3):
while (a <= b)
{
int special = 1;
if (a%4 == 0 || a%9 == 0)
{
special = 0;
}
else for (int z=5,c=2; z<=lim; z+=c,c=6-c)
{
if (a % (z * z) == 0)
{
special = 0;
break;
}
}
...
}
Другие решения