Автор | Сообщение |
|
Отправлено: 24.03.21 23:06. Заголовок: Задача 25
Не могу понять ошибка в коде: Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество четных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания. for n in range(35000000, 40000000+1): if n%2!=0: a = [1,n] # 2 делителя: 1 и число n else: a = [1] # 1 делитель: число 1 d = 2 while d*d <= n: if d%2!=0:# добавляем НЕЧЁТН делитель a.append(d)# добавляем НЕЧЁТН делитель if n//d != d and (n//d)%2!=0: # исключаем квадрат a.append(n//d)# добавляем нечетный парный делитель if len(a)>5: break d += 1 if len(a)==5: print(n)
|
|
|
Ответов - 17
, стр:
1
2
All
[только новые]
|
|
|
Отправлено: 28.03.21 20:10. Заголовок: Поляков пишет: Все ..
Поляков пишет: цитата: | Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны. |
| Да, безусловно, я этим и руководствовался при решении задач, где у нас нечетное количество делителей. Однако здесь же у нас речь о количестве только нечетных делителей, а значит, мы можем иметь ситуацию, когда у нас будет две пары по 2 нечетных числа (1 & само число, и еще одна пара), еще 1 нечетный делитель (итого, как нам и нужно в условии, получаем 5 нечетных), однако в пару к нему будет идти чётный делитель. В таком случае, пары, состоящей из квадратных корней из исходного числа, нет. Разве не может быть такой ситуации?
|
|
|
|
Отправлено: 30.03.21 13:53. Заголовок: def isPrime( x ): ..
def isPrime( x ): if x <= 1: return False d = 3 while d*d <= x: if x % d == 0: return False d += 2 return True start, end = 35000000, 40000000 from math import sqrt for n in range(start, end+1): x = n while x % 2 == 0: x //= 2 qX = round(sqrt(sqrt(x))) if qX**4 == x and isPrime(qX): print( n, x ) небольшая оптимизация сокращает на треть время выполнения (46 против 31 секунды на onlinegdb.com) def isPrime( x ): if x <= 1: return False d = 3 while d*d <= x: if x % d == 0: return False d += 2 return True нет смысла проверять делимость на четные числа, мы их отбросили if qX**4 == x and isPrime(qX): меняем порядок проверки. Если число не имеет целочисленного корня четвертой степени, то нет смысла проходить по циклу поиска делителей
|
|
|
Ответов - 17
, стр:
1
2
All
[только новые]
|
|