Форум » Обработка целых чисел » Задача 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

nikson: Нашел ошибку: потерял if n%d==0: :))) [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 n%d==0:# проверяем делимость 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]

nikson: Предыдущий код считает долго, поэтому надо добавить проверку квадрата числа (тогда время выполнения кода 4 с): [pre2] for n in range(35000000, 40000000+1): if n%2!=0: a = [1,n] # 2 делителя: 1 и число n else: a = [1] # 1 делитель: число 1 if int(n**0.5)**2 == n: d = 2 while d*d <= n: if n%d==0: 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]

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] меняем порядок проверки. Если число не имеет целочислинного корня четвертой степени, то нет смысла проходить по циклу поиска делителей


nikson: Ответ: 38950081 (его делители 1 79 6241 493039 38950081) 39337984 ( его делители 1 7 49 343 2401)

nikson: И все же пропускает некоторые числа, например на интервале до 700, пропускает 162, 324

nikson: Вот итоговый код на задачу. [pre2] # ищем простые числа, 4я степень # которых <= 45 000 000 b = [] # массив хранения простых делителей otv = []# массив хранения чисел для ответа на задачу k = int(45000000**0.25) for i in range(2, k+1): count = 2 # делители: 1 и само число for j in range(2,round(i**0.5)+1): # другие делители if i%j == 0: count = 0 break # число уже не простое if count == 2: b.append(i) for n in range(35000000, 40000000+1): if n%2!=0: a = [1,n] # 2 делителя: 1 и число n else: a = [1] # 1 делитель: число 1 if int(n**0.25)**4 == n: # число явл-ся 4ю степенью d = 2 while d*d <= n: if n%d==0: 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: otv.append(n) for x in range(1,len(b)): c = 2 # 2,4,8,16 while (b[x]**4)*c <=40000000: rez = (b[x]**4)*c c*=2 if rez>=35000000: otv.append(rez) print(*sorted(otv)) [/pre2]

nikson: ответ: 35819648 38950081 39037448 39337984

nikson: Первый блок FOR для чисел, которые являются простыми числами 4й степени. Например у числа 81 - пять нечетных делителей: 1, 3, 9, 27, 81. 81 - это 3^4. Также этот блок подходит и к другим подобным числам, например 625: 1, 5, 25, 125, 625 То есть ситуация, когда ЧЁТНЫХ делителей у числа нет.

Поляков: [pre2] def isPrime( x ): if x <= 1: return False d = 2 while d*d <= x: if x % d == 0: return False d += 1 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 isPrime(qX) and qX**4 == x: print( n, x )[/pre2]

nikson: Поляков пишет: if isPrime(qX) and qX**4 == x: Оказывается так просто :))) Спасибо.

Поляков: stncr пишет: В таком случае, пары, состоящей из квадратных корней из исходного числа, нет. Разве не может быть такой ситуации? Обратите внимание, что я говорю о ситуации, когда все двойки мы уже извлекли:[pre2]while x % 2 == 0: x //= 2 [/pre2]То есть четных делителей не осталось.

nikson: Другая ситуация, когда у числа кроме нечетных делителей есть хоть 1 четный делитель. Например у числа 162 есть делители: 1, 2, 3, 6, 9, 18, 27, 54, 81, 162. Тогда нужно проверять наличие пары: простого минимального нечетного числа в 4й степени и четного делителя. первый такой = 2 (в коде переменная С). Второй уже 4 и т.д.

Поляков: nikson пишет: Другая ситуация, когда у числа кроме нечетных делителей есть хоть 1 четный делитель. Единственный чётный простой делитель - это 2. Поэтому нужно извлекать степень двойки (делить, пока делится). А дальше остались только нечетные. И это число должно быть 4-й степенью простого числа.

stncr: Может кто-нибудь объяснить, на каком основании при поиске 5 нечетных делителей мы пришли к тому, что нужные нам числа - квадраты? Как, при выпадении этой задачи на экзамене, к этому нужно было придти? :)

Поляков: stncr пишет: на каком основании при поиске 5 нечетных делителей мы пришли к тому, что нужные нам числа - квадраты Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны.



полная версия страницы