Автор | Сообщение |
|
Отправлено: 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
[только новые]
|
|
|
Отправлено: 25.03.21 00:11. Заголовок: Нашел ошибку: потеря..
Нашел ошибку: потерял if n%d==0: :))) 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)
|
|
|
|
Отправлено: 25.03.21 00:38. Заголовок: Предыдущий код счита..
Предыдущий код считает долго, поэтому надо добавить проверку квадрата числа (тогда время выполнения кода 4 с): 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)
|
|
|
|
Отправлено: 30.03.21 13:51. Заголовок: 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): меняем порядок проверки. Если число не имеет целочислинного корня четвертой степени, то нет смысла проходить по циклу поиска делителей
|
|
|
|
Отправлено: 25.03.21 00:39. Заголовок: Ответ: 38950081 (его..
Ответ: 38950081 (его делители 1 79 6241 493039 38950081) 39337984 ( его делители 1 7 49 343 2401)
|
|
|
|
Отправлено: 25.03.21 01:46. Заголовок: И все же пропускает ..
И все же пропускает некоторые числа, например на интервале до 700, пропускает 162, 324
|
|
|
|
Отправлено: 25.03.21 11:44. Заголовок: Вот итоговый код на ..
Вот итоговый код на задачу. # ищем простые числа, 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))
|
|
|
|
Отправлено: 25.03.21 11:45. Заголовок: ответ: 35819648 3895..
ответ: 35819648 38950081 39037448 39337984
|
|
|
|
Отправлено: 25.03.21 11:51. Заголовок: Первый блок FOR для ..
Первый блок FOR для чисел, которые являются простыми числами 4й степени. Например у числа 81 - пять нечетных делителей: 1, 3, 9, 27, 81. 81 - это 3^4. Также этот блок подходит и к другим подобным числам, например 625: 1, 5, 25, 125, 625 То есть ситуация, когда ЧЁТНЫХ делителей у числа нет.
|
|
|
|
| Администратор
|
Сообщение: 2619
|
|
Отправлено: 25.03.21 11:52. Заголовок: def isPrime( x ): ..
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 )
|
|
|
|
Отправлено: 25.03.21 12:11. Заголовок: Поляков пишет: if ..
Поляков пишет: цитата: | if isPrime(qX) and qX**4 == x: |
| Оказывается так просто :))) Спасибо.
|
|
|
|
| Администратор
|
Сообщение: 2641
|
|
Отправлено: 28.03.21 20:17. Заголовок: stncr пишет: В таком..
stncr пишет: цитата: | В таком случае, пары, состоящей из квадратных корней из исходного числа, нет. Разве не может быть такой ситуации? |
|
Обратите внимание, что я говорю о ситуации, когда все двойки мы уже извлекли: цитата: | while x % 2 == 0: x //= 2 |
|
То есть четных делителей не осталось.
|
|
|
|
|
Отправлено: 25.03.21 12:02. Заголовок: Другая ситуация, ког..
Другая ситуация, когда у числа кроме нечетных делителей есть хоть 1 четный делитель. Например у числа 162 есть делители: 1, 2, 3, 6, 9, 18, 27, 54, 81, 162. Тогда нужно проверять наличие пары: простого минимального нечетного числа в 4й степени и четного делителя. первый такой = 2 (в коде переменная С). Второй уже 4 и т.д.
|
|
|
|
| Администратор
|
Сообщение: 2620
|
|
Отправлено: 25.03.21 12:05. Заголовок: nikson пишет: Другая..
nikson пишет: цитата: | Другая ситуация, когда у числа кроме нечетных делителей есть хоть 1 четный делитель. |
|
Единственный чётный простой делитель - это 2. Поэтому нужно извлекать степень двойки (делить, пока делится). А дальше остались только нечетные. И это число должно быть 4-й степенью простого числа.
|
|
|
|
Отправлено: 28.03.21 17:49. Заголовок: Может кто-нибудь объ..
Может кто-нибудь объяснить, на каком основании при поиске 5 нечетных делителей мы пришли к тому, что нужные нам числа - квадраты? Как, при выпадении этой задачи на экзамене, к этому нужно было придти? :)
|
|
|
|
| Администратор
|
Сообщение: 2635
|
|
Отправлено: 28.03.21 17:57. Заголовок: stncr пишет: на как..
stncr пишет: цитата: | на каком основании при поиске 5 нечетных делителей мы пришли к тому, что нужные нам числа - квадраты |
|
Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны.
|
|
|
|
Отправлено: 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
[только новые]
|
|