На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 6
ссылка на сообщение  Отправлено: 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;
}
}
}

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 2 [только новые]







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


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

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

Discussio mater veritas est Спасибо: 1 
ПрофильЦитата Ответить



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


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

Спасибо: 0 
ПрофильЦитата Ответить
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 5035
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет