На этом форуме отвечают на конкретные вопросы. Фраза «я не понимаю, как решать» — это не вопрос. На вопрос «как решить задачу №X» вас отошлют к материалам сайта kpolyakov.spb.ru. За бессвязный поток слов и неспособность формулировать свои мысли — бан.

Если у вас не сходится ответ на какую-то задачу, пожалуйста сразу представляйте свое «правильное» решение.
Программы "заворачивайте" в тэг [pre2]...[/pre2], при этом сохраняются все отступы и применяется моноширинный шрифт. Если у вас используется сочетание "[i]" для обозначения элемента массива или строки, ставьте пробел после открывающей скобки. Иначе система выделит все дальнейшее курсивом.

Для регистрации на форуме щелкните по ссылке «Вход-регистрация» вверху страницы. В открывшееся окошко «ник» введите свою фамилию на русском языке (например, Иванов). В окошко «пароль» введите придуманный вами пароль, состоящий из латинских букв и цифр. Поставьте галочку в окошке «зарегистрироваться, я новый участник» и нажмите кнопку «ОК».

АвторСообщение



Сообщение: 129
ссылка на сообщение  Отправлено: 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)


Спасибо: 1 
ПрофильЦитата Ответить
Ответов - 17 , стр: 1 2 All [только новые]





Сообщение: 133
ссылка на сообщение  Отправлено: 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)


Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 134
ссылка на сообщение  Отправлено: 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)


Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 1
ссылка на сообщение  Отправлено: 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):

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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 135
ссылка на сообщение  Отправлено: 25.03.21 00:39. Заголовок: Ответ: 38950081 (его..


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 136
ссылка на сообщение  Отправлено: 25.03.21 01:46. Заголовок: И все же пропускает ..


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

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 137
ссылка на сообщение  Отправлено: 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))


Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 138
ссылка на сообщение  Отправлено: 25.03.21 11:45. Заголовок: ответ: 35819648 3895..


ответ:
35819648
38950081
39037448
39337984

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 139
ссылка на сообщение  Отправлено: 25.03.21 11:51. Заголовок: Первый блок FOR для ..


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 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 )


___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 141
ссылка на сообщение  Отправлено: 25.03.21 12:11. Заголовок: Поляков пишет: if ..


Поляков пишет:

 цитата:
if isPrime(qX) and qX**4 == x:


Оказывается так просто :)))
Спасибо.

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 2641
ссылка на сообщение  Отправлено: 28.03.21 20:17. Заголовок: stncr пишет: В таком..


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

Обратите внимание, что я говорю о ситуации, когда все двойки мы уже извлекли:
 цитата:
while x % 2 == 0: x //= 2 

То есть четных делителей не осталось.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 140
ссылка на сообщение  Отправлено: 25.03.21 12:02. Заголовок: Другая ситуация, ког..


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 2620
ссылка на сообщение  Отправлено: 25.03.21 12:05. Заголовок: nikson пишет: Другая..


nikson пишет:
 цитата:
Другая ситуация, когда у числа кроме нечетных делителей есть хоть 1 четный делитель.

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

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Не зарегистрирован
ссылка на сообщение  Отправлено: 28.03.21 17:49. Заголовок: Может кто-нибудь объ..


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

Спасибо: 0 
ПрофильЦитата Ответить
Администратор




Сообщение: 2635
ссылка на сообщение  Отправлено: 28.03.21 17:57. Заголовок: stncr пишет: на как..


stncr пишет:
 цитата:
на каком основании при поиске 5 нечетных делителей мы пришли к тому, что нужные нам числа - квадраты

Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны.

___________________________________________________
Имей мужество пользоваться собственным умом. (И. Кант)
Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 1
ссылка на сообщение  Отправлено: 28.03.21 20:10. Заголовок: Поляков пишет: Все ..


Поляков пишет:

 цитата:
Все делители числа N группируются в пары: d и N//d. Если делителей нечетное число, в одной из пар два делителя равны.



Да, безусловно, я этим и руководствовался при решении задач, где у нас нечетное количество делителей. Однако здесь же у нас речь о количестве только нечетных делителей, а значит, мы можем иметь ситуацию, когда у нас будет две пары по 2 нечетных числа (1 & само число, и еще одна пара), еще 1 нечетный делитель (итого, как нам и нужно в условии, получаем 5 нечетных), однако в пару к нему будет идти чётный делитель. В таком случае, пары, состоящей из квадратных корней из исходного числа, нет. Разве не может быть такой ситуации?

Спасибо: 0 
ПрофильЦитата Ответить



Сообщение: 2
ссылка на сообщение  Отправлено: 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):

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

Спасибо: 0 
ПрофильЦитата Ответить
Ответов - 17 , стр: 1 2 All [только новые]
Ответ:
1 2 3 4 5 6 7 8 9
видео с youtube.com картинка из интернета картинка с компьютера ссылка файл с компьютера русская клавиатура транслитератор  цитата  кавычки оффтопик свернутый текст

показывать это сообщение только модераторам
не делать ссылки активными
Имя, пароль:      зарегистрироваться    
Тему читают:
- участник сейчас на форуме
- участник вне форума
Все даты в формате GMT  3 час. Хитов сегодня: 4420
Права: смайлы да, картинки да, шрифты нет, голосования нет
аватары да, автозамена ссылок вкл, премодерация откл, правка нет