Отправлено: 04.11.20 18:04. Заголовок: Задача 25 из СтатГрад от 22.10.2020

Задача:
Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 6 есть два нетривиальных делителя: 2 и 3. Найдите все натуральные числа, принадлежащие отрезку [123456789; 223456789] и имеющие ровно три нетривиальных делителя. Для каждого найденного числа запишите в ответе его наибольший нетривиальный делитель. Ответы расположите в порядке возрастания.

Подскажите, пожалуйста, как оптимизировать программу. В DEV С++ работает 15 минут. Для экзамена это слишком большое время...

#include <iostream>
#include<cmath>
using namespace std;

int main()
{
for( int n = 123456789; n <= 223456790; n++ )
{
// if (n%10000000 == 0)
// cout << "Обрабатывается число > " << n << "\n";
int k = 2;//сразу посчитала 1 и само число n
int d = 2;
int maxd = 1;
int q = sqrt(n);
if (q == round(sqrt(n))) //если корень из числа целый, то
{ //у этого числа нечётное количество делителей
while (d < q)
{
if(n % d == 0)
{
k +=2; //сразу прибавляю парный делитель
if(maxd < n/d)
maxd = n/d;
}
d++;
if (d*d == n)
k++;
if (k > 5)
break;
}
if( k == 5 )
cout << "!n="<<n<<" "<<"k="<< k <<" "<< maxd << endl;
}
}
}

 Отправлено: 04.11.20 19:26. Заголовок: В общем небольшой фа..

В общем небольшой факт из теории чисел: ровно три нетривиальных делителя только у чисел вида p^4 (p-простое число).
Поэтому берём корни 4 степени из концов диапазона [123456789; 223456789] -> [106; 122]
Проверять можно числа вида i**4

Главная мысля на данный момент : Диапазоны размером более миллиона необходимо сжимать на несколько порядков

 Отправлено: 08.11.20 13:43. Заголовок: Спасибо большое, Але..

Спасибо большое, Алексей!