Форум » Обработка целых чисел » Задача 25 » Ответить
Задача 25
nikson: Не могу понять ошибка в коде: Найдите все натуральные числа, принадлежащие отрезку [35 000 000; 40 000 000], у которых ровно пять различных нечётных делителей (количество четных делителей может быть любым). В ответе перечислите найденные числа в порядке возрастания. [pre2] 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) [/pre2]
Ответов - 17, стр:
1 2 All
stncr: Поляков пишет: Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны. Да, безусловно, я этим и руководствовался при решении задач, где у нас нечетное количество делителей. Однако здесь же у нас речь о количестве только нечетных делителей, а значит, мы можем иметь ситуацию, когда у нас будет две пары по 2 нечетных числа (1 & само число, и еще одна пара), еще 1 нечетный делитель (итого, как нам и нужно в условии, получаем 5 нечетных), однако в пару к нему будет идти чётный делитель. В таком случае, пары, состоящей из квадратных корней из исходного числа, нет. Разве не может быть такой ситуации?
ASM: [pre2]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 )[/pre2] небольшая оптимизация сокращает на треть время выполнения (46 против 31 секунды на onlinegdb.com) [pre2]def isPrime( x ): if x <= 1: return False d = 3 while d*d <= x: if x % d == 0: return False d += 2 return True[/pre2] нет смысла проверять делимость на четные числа, мы их отбросили [pre2]if qX**4 == x and isPrime(qX):[/pre2] меняем порядок проверки. Если число не имеет целочисленного корня четвертой степени, то нет смысла проходить по циклу поиска делителей
полная версия страницы