C/C++

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

Рассматривается множество целых чисел, принадлежащих числовому отрезку [56123; 97354], которые имеют более 35 делителей. Найдите количество таких чисел и их среднее арифметическое. В ответе запишите через пробел сначала количество, а потом – целую часть среднего арифметического.
СЗ
Сеймур Зейналов
122
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

Похожие вопросы