Отправлено: 05.01.22 16:24. Заголовок: №2574 (24.25) (проблема с алгоритмом)

Здравствуйте! В задаче нужно найти такие числа из отрезка, у которых ровно 5 различных делителей.

Вместо перебора в ответах предложен следующий алгоритм:

from math import sqrt 
  
 start, end = 11275, 16328 
  
 qStart = int(sqrt(start)) 
 qEnd = int(sqrt(end))+1 
 for q in range( qStart, qEnd+1 ): 
   n = q*q 
   a = [q] # массив для хранения делителей 
   for d in range(1, q): 
     if n % d == 0: 
       a = a + [d, n//d] 
       if len(a) > 5: break 
   if len(a) == 5: 
     print( *sorted(a) )

Проблема в том, что если при извлечении корня из левой границы после округления получится квадрат простого числа, но при этом сама левая граница не является квадратом числа, то алгоритм сработает неправильно. Например, если передвинуть левую границу к start = 11**4 + 1 (14642), то алгоритм выдаст такой же ответ "1 11 121 1331 14641", хотя числа 14641 нет в диапазоне.

Также алгоритм можно ускорить: идея алгоритма заключается в том, чтобы перебирать не каждое число из диапазона, а только те числа, из которых можно извлечь квадрат, и дальше ищется количество множителей до корня из числа (которое в свою очередь само является корнем из числа из диапазона). Ускорение заключается в том, что нам не нужно искать эти множители, поскольку получившееся число q должно быть само квадратом простого числа. Тогда нужно всего лишь проверить, извлекается ли корень из q и является ли полученный корень простым числом. Во-первых, вложенный цикл будет работать не для каждого q, а только для тех, из которых извлекается корень. Во-вторых, вложенный цикл будет проходиться каждый раз не до корня из числа из диапазона, а до корня четвертой степени из этого числа. В-третьих, при проверке на простоту не нужно перебирать каждое число, а только нечетные (+ отдельная проверка на четность), когда при поиске всех корней цикл идет с шагом 1.

 Отправлено: 06.01.22 12:36. Заголовок: В простом решении да..

В простом решении данной задачи важно знать формулу нахождения количества различных делителей числа. a=p1^s1·p2^s2·…·pn^sn, где a - само число, pi - простой множитель числа, si - степень простого множителя. Исходя из этого, количество равно произведению всех степеней простых множителей + 1, т. е. S = (s1+1)*(s2+1)*...*(sn+1). В этой задаче 5 делителей требуется. 5, в свою очередь, простое число => требуемые числа будут простыми числами в четвертой степени. Такое число в данной задаче всего одно.

from math import ceil

a = 11275
b = 16328
start = int(ceil(a ** 0.25))
end = int(b ** 0.25)
print(start, end)
print(start ** 2, start ** 3)

"Решение", естественно, привел для частного случая.

 Отправлено: 06.01.22 13:33. Заголовок: zachto это все понят..

zachto это все понятно. Прочитайте еще раз вдумчиво

цитата:

если передвинуть левую границу к start = 11**4 + 1 (14642), то алгоритм выдаст такой же ответ "1 11 121 1331 14641", хотя числа 14641 нет в диапазоне

В Вашем алгоритме такая же проблема. Стоит сместить границу (a = 14642), и он выдает неверный ответ "144 1728". Вы не не проверяете округления и это заканчивается закономерно.

 Отправлено: 06.01.22 14:17. Заголовок: Вы хотите с помощью ..

Вы хотите с помощью одного тривиального алгоритма решить все задачи подобного плана? Могу лишь пожелать удачи. Если в моем алгоритме a - 14642, то start = 12, а end = 11 => чисел вообще нет. В ЕГЭ нужно не только программировать, но и думать немного, смотреть на входные данные задачи.

 Отправлено: 06.01.22 14:27. Заголовок: Вы хотите с помощью ..

цитата:

Вы хотите с помощью одного тривиального алгоритма решить все задачи подобного плана?

zachto, а это так сложно? Правда?

цитата:

Могу лишь пожелать удачи.

Могу лишь пожелать удачи с частными решениями. У меня для Вас есть куда лучше вариант "print(121, 1331)" - как Вам? Что будете делать, если после извлечения корня четвертой степени из a и округления, в a окажется не простое число? Опять рассказывать про частные решения "половина в голове, половина в коде"?

цитата:

Если в моем алгоритме a - 14642, то start = 12, а end = 11 => чисел вообще нет.

Если Ваш алгоритм запустить, то он скажет обратное. Попробуйте сами.

a = 14642 
 b = 16328 
 start = int(ceil(a ** 0.25)) 
 end = int(b ** 0.25) 
 print(start, end) 
 print(start ** 2, start ** 3)

цитата:

В ЕГЭ нужно не только программировать, но и думать немного, смотреть на входные данные задачи.

Мир не заканчивается ЕГЭ, во-первых. Во-вторых, вот именно, что думать нужно. Вы как пришли к выводу, что в диапазоне единственное число существует?

 Отправлено: 06.01.22 14:38. Заголовок: Вы как пришли к выво..

цитата:

Вы как пришли к выводу, что в диапазоне единственное число существует?

Чисел существует не более чем start - end + 1.

цитата:

Что будете делать, если после извлечения корня четвертой степени из a и округления, в a окажется не простое число?

Вижу простое число => ok.
Вижу составное число => программно ищу ближайшее простое, большее a.

цитата:

Если Ваш алгоритм запустить, то он скажет обратное. Попробуйте сами.

Перед отправкой я всегда проверяю код, start = 12, end = 11.

цитата:

У меня для Вас есть куда лучше вариант "print(121, 1331)" - как Вам?

Отлично, на ЕГЭ по информатике никто не смотрит ни на код, ни на какое-либо решение. Может быть вам в молитве пришел ответ, nobody cares.

цитата:

а это так сложно? Правда?

Нужно уметь комбинировать решения, на мой взгляд, естественно.

 Отправлено: 06.01.22 14:47. Заголовок: Чисел существует не ..

цитата:

Чисел существует не более чем start - end + 1.

Нет же, это опять ошибка. Вы тут себя поправляете с моей помощью:

цитата:

Вижу простое число => ok. Вижу составное число => программно ищу ближайшее простое, большее a.

Отлично, что Вам Ваш глаз скажет на счет числа 6117 - простое или составное?

цитата:

Перед отправкой я всегда проверяю код, start = 12, end = 11.

Потрясающее решение, где все в ручном режиме.

цитата:

Отлично, на ЕГЭ по информатике никто не смотрит ни на код, ни на какое-либо решение. Может быть вам в молитве пришел ответ, nobody cares.

Вы егэ сдаете и учитесь программировать для чего? Чтобы навыки развить или грамоту на стенку повесить?

цитата:

Нужно уметь комбинировать решения, на мой взгляд, естественно.

Нужно уметь решать задачи в общем виде, особенно, когда это не сложно, не знаю, где учат обратному. Вы и по математике-физике на половине решения в формулы числа подставляете?

Написать общее решение намного проще и быстрее, чем что-то там проверять глазами. Если в диапазоне окажется не 1, а 3 числа, что делать будете? Опять костыли придумывать? Выводить в консоль каждое число и работать вручную?

 Отправлено: 06.01.22 16:15. Заголовок: Нет же, это опять ош..

цитата:

Нет же, это опять ошибка. Вы тут себя поправляете с моей помощью:

Надеюсь, вы знаете что значит "не более чем".

цитата:

Отлично, что Вам Ваш глаз скажет на счет числа 6117 - простое или составное?

Сумма цифр кратна 3 => число составное.

цитата:

Вы и по математике-физике на половине решения в формулы числа подставляете?

Удивительно, что это пишите Вы. Человек, который хочет "уметь решать задачи в общем виде" и просто подставлять значения в программу.

цитата:

Написать общее решение намного проще и быстрее, чем что-то там проверять глазами. Если в диапазоне окажется не 1, а 3 числа, что делать будете? Опять костыли придумывать? Выводить в консоль каждое число и работать вручную?

А что быстрее на экзамене? Вспомнить какое-то там общее решение или сразу написать "костыль"?

цитата:

Нужно уметь решать задачи в общем виде, особенно, когда это не сложно, не знаю, где учат обратному.

Нужно лишь понять условие задачи. Общие решения оставьте на олимпиады по проге, физику и математику.

 Отправлено: 06.01.22 16:35. Заголовок: Надеюсь, вы знаете ч..

цитата:

Надеюсь, вы знаете что значит "не более чем".

Принято.

цитата:

Удивительно, что это пишите Вы. Человек, который хочет "уметь решать задачи в общем виде" и просто подставлять значения в программу.

Удивительно, что это пишет человек, который с разметкой справится не может. Смысл был не в этом же. 8341 простое число? Как там Ваш глаз?

цитата:

А что быстрее на экзамене? Вспомнить какое-то там общее решение или сразу написать "костыль"?

Я же написал, что быстрее и проще. Может Вы и заучиваете какие-то там решения, но я их в состоянии писать не вспоминая. Как раз куда проще решить задачу в общем виде, чем заботиться обо всех исключениях и писать "костыли".

цитата:

Нужно лишь понять условие задачи. Общие решения оставьте на олимпиады по проге, физику и математику.

Еще раз, Ваш алгоритм работает из-за везения. Вы получаете диапазон [a, b] - как вы с ходу скажете, сколько там есть чисел, из которых можно извлечь корень четвертой степени? Как вы определите на глаз простое число или нет? Каждый раз сидеть с консолью и рассматривать каждый шаг? Это не решение, а мазохизм.

 Отправлено: 06.01.22 17:46. Заголовок: Удивительно, что это..

цитата:

Удивительно, что это пишет человек, который с разметкой справится не может.

Зря тему переводите.

цитата:

чем заботиться обо всех исключениях и писать "костыли"

Непонятно о каких исключениях нужно заботиться и какие костыли нужно писать. Печально, что вы не научились мыслить аналитически за все годы в школе.

цитата:

Я же написал, что быстрее и проще.

Что проще? Знать, что квадрат двух равен четырем, или писать лишнюю строку кода?

цитата:

Вы получаете диапазон [a, b]

Я получаю конкретный отрезок, а не [a, b]. Получу один отрезок - решу одним способом, получу другой - другим.

цитата:

Еще раз, Ваш алгоритм работает из-за везения.

У меня, у автора алгоритма, конечно же, везение, хороший отрезок, специально подобранные числа и т.п. Дайте другие входные данные - изменим алгоритм и решим по-другому.

 Отправлено: 06.01.22 18:29. Заголовок: Зря тему переводите...

цитата:

Зря тему переводите.

Нет же, это Вы решили извернуться с кратностью на три. Если Вы такой щепетильный, то почему пропусти вопрос про 8341? Я надеюсь, Вы же с первого раза поняли, что я хотел сказать, и решили ускользнуть, перейдя на личности, а теперь обижаетесь.

цитата:

Непонятно о каких исключениях нужно заботиться и какие костыли нужно писать.

Я могу повторить, я уже заметил, что у вас проблемы:
1) Ваш алгоритм работает в ручном режиме, нужно постоянно что-то смотреть и додумывать
2) он не универсальный, что будете делать, если в диапазоне больше 1 числа?
3) как проверять полученные числа на простоту?

По-сути, это даже не алгоритм, а подгонка "решения" под результат. Смени чуть-чуть диапазон и снова придется половину решать в голове. Вы просто вручную исследуете диапазон и надеетесь на легкий ответ.

цитата:

Печально, что вы не научились мыслить аналитически за все годы в школе.

И это говорит человек, для которого общие решения затруднительны.

цитата:

Что проще? Знать, что квадрат двух равен четырем, или писать лишнюю строку кода?

Я уже написал несколько раз, что проще. Зачем Вы мне из раза в раз задаете один и тот же вопрос, надеясь услышать оправдывающий Вас ответ? Вместо того, чтобы делать половину действий вручную и просматривать консоль, проще написать пару лишних строк кода, которые вовсе не лишние, потому что если исключений будет чуть больше, Вы сами запутаетесь в своем решении и половину ЕГЭ просидите, ковыряя консоль.

цитата:

У меня, у автора алгоритма, конечно же, везение, хороший отрезок, специально подобранные числа и т.п.

Не приписывайте себя к автору. У автора есть недочет, случай, который он не учел. Это сразу понятно. У Вас же это какое-то полуручное недоразумение, а не алгоритм.

цитата:

Дайте другие входные данные - изменим алгоритм и решим по-другому.

Ага, очередной велосипед с квадратными колесами на ручном управлении. Ваш уровень решений я понял, спасибо. Мне с Вами обсуждать нечего.

 Отправлено: 07.01.22 23:04. Заголовок: beep пишет: Проблема..

beep пишет:

цитата:

Проблема в том, что если при извлечении корня из левой границы после округления получится квадрат простого числа, но при этом сама левая граница не является квадратом числа, то алгоритм сработает неправильно.

Спасибо, решение поправил.

цитата:

Также алгоритм можно ускорить: идея алгоритма заключается в том, чтобы перебирать не каждое число из диапазона, а только те числа, из которых можно извлечь квадрат, и дальше ищется количество множителей до корня из числа (которое в свою очередь само является корнем из числа из диапазона).

Да, можно. Но нет особой необходимости. Это не критично при заданных данных, но усложнит программу и повысит вероятность ошибки.

 Отправлено: 08.01.22 09:54. Заголовок: Поляков, Спасибо, р..

Поляков,

цитата:

Спасибо, решение поправил.

Вам спасибо за Вашу работу. Можете, пожалуйста, посмотреть соседнюю тему? В материалах для подготовки этот алгоритм тоже рассматривается, как общий, и там тоже есть недочет, который не заметен из-за того, что диапазон удачный попался. Алгоритм будет неправильно срабатывать на любое простое число в 4й степени (алгоритм будет считать, что у такого числа 4 корня, хотя их на самом деле 5) - http://egekp.unoforum.pro/?1-22-0-00000157-000-0-0-1641482077

цитата:

Да, можно. Но нет особой необходимости.

Это просто до кучи уже, раз тема создана. Вдруг кому-нибудь пригодится.

 Отправлено: 08.01.22 11:55. Заголовок: Поляков, в решении д..

Поляков, в решении для задачи 25.91 (№2595) тот же алгоритм и та же проблема, левая граница не проверяется на вхождение, если взять число чуть большее квадрата простого числа, то алгоритм снова учтет число, которого нет в диапазоне.

 Отправлено: 08.01.22 12:05. Заголовок: beep пишет: в решени..

beep пишет:

цитата:

в решении для задачи 25.91 (№2595) тот же алгоритм и та же проблема

Там есть проверка диапазона.

 Отправлено: 11.01.22 12:51. Заголовок: Поляков, моя невнима..

Поляков, моя невнимательность (проще один раз проверить, чем каждый раз в цикле), извините.