C/C++

Информатика, C++, задание

Рассматривается множество целых чисел, принадлежащих числовому отрезку [56123; 97354], которые имеют более 35 делителей. Найдите количество таких чисел и их среднее арифметическое. В ответе запишите через пробел сначала количество, а потом – целую часть среднего арифметического.
int test(int a){ int c=1;for(int i=2;i<=a;i++)if(a%i==0)cnt++; return cnt; }


...
cnt=0;sum=0;
for(int i=56123;i <= 97354;i++)if(test(i) > 35){ cnt++; sum+=i; }
cout<<cnt<<" "<<sum/cnt;
...
Sasha Alankin
Sasha Alankin
54 961
Лучший ответ
Anvar Hatamov В таком виде уже и распараллеливать можно. Чуть ли не 5 секунд.
Можно ускорить - делители считать до i<=a>>2. И остается вопрос насчет 1 - это тоже делитель. Так что любое число кроме 1 имеет как минимум два делителя - 1 и само себя.
#include <cmath>
#include <iostream>
int main() { int i, j, k, l = 0, m; double s = 0;
for (i = 56123; i < 97355; i++) { k = 0; m = sqrt(i);
for (j = 1; j <= m; j++) if (i % j == 0) k += 2;
if (m * m == i) k--; if (k > 35) { ++l; s += i; } }
std::cout << l << ' ' << (int) s / l; }
Виталий Гунько
Виталий Гунько
66 572
Anvar Hatamov https://codeshare.io/1YLPp0
Благодарю за критику.
Переписал программу, теперь вычисляет правильно и очень быстро. Но нуждается в таблице простых чисел (которую сама вычисляет довольно таки долго). А ваш алгоритм так и не нашел. Это точно алгоритмика или математика?
 #include 
#include
#include
#include

std::atomic_int32_t glob_cnt{}, glob_sum{};

bool test(const int& a)
{
int cnt{};
int p = a >> 2;
for (int i = 2; i 33) return true;
}
return false;
}

void compute(int a, int b)
{
int cnt{}, sum{};
for (int i = a; i < b; i++) if (test(i)) { cnt++; sum += i; };
glob_cnt += cnt;
glob_sum += sum;
}

int main()
{
std::vector threads;
constexpr int a = 56123;
constexpr int b = 97354;
constexpr int dis = b - a;
constexpr int h = dis / 8;
int an = a;
for (int i = 0; i < 8; i++)
{
threads.emplace_back(std::thread{ compute,an, an + h });
an += h + 1;
}
for (auto& i : threads) i.join();
std::cout
Антон Яковлев
Антон Яковлев
51 416