Форум » Обработка целых чисел » Задача 25 из СтатГрад от 22.10.2020 » Ответить
Задача 25 из СтатГрад от 22.10.2020
Lilianna_: Задача: Назовём нетривиальным делителем натурального числа его делитель, не равный единице и самому числу. Например, у числа 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; } } }
Ответов - 2
cabanov.alexey: В общем небольшой факт из теории чисел: ровно три нетривиальных делителя только у чисел вида p^4 (p-простое число). Поэтому берём корни 4 степени из концов диапазона [123456789; 223456789] -> [106; 122] Проверять можно числа вида i**4 Главная мысля на данный момент : Диапазоны размером более миллиона необходимо сжимать на несколько порядков
Lilianna_: Спасибо большое, Алексей!
полная версия страницы