Простые делители числа 13195 - это 5, 7, 13 и 29.
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Для решения этой задачи я взял пример как разложить число на простые делители:
И исходя из этого примера и написал алгоритм по нахождению самого большого делителя.
И исходя из этого примера и написал алгоритм по нахождению самого большого делителя.
num = 600851475143
count = 2
while 1:
if num % count == 0:
num /= count
if num == 1:
print(count)
break
count += 1
- Возьмем заданной число и поделим его на два. Если делится без остатка - знат 2 простой делитель. Если не делится - знать делаем 2 + 1 и делим заданной число на 3.
- После нахождения первого делителя, делим на него число из задачи и вписываем его на место оригинального числа.
- Повторяем луп пока то число что мы проверяем не будет равно одному.
- Выдаем это самое значение при котором проверочное число равно одному.
Мой ответ 6857.
Я так решил.
ода) казалось бы все так просто, но я бы фиг додумался
ОтветитьУдалитьПочему тогда с число 1421 не работает?
ОтветитьУдалитьневерно) есть делители больше
ОтветитьУдалить716151937
Удалитьтам else надо добавить перед count += 1, иначе программа будет криво работать
ОтветитьУдалитьnum = 600851475143
ОтветитьУдалитьdiv = []
for i in range(1, num):
if (num % i == 0):
div.append(i)
print(max(div))
этот код пайтон думает очень долго 😂😂😂
num = 600851475143
Удалитьdiv = []
for i in range(2, num):
if (num % i == 0):
div = num / i
print(div)
так же долго думает но ответ получим уже в первой строке
в конце брейк тыкнут и вообще проблем не будет
УдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьКод сверху работает только если данное число - произведение простых без повторных множителей...
ОтветитьУдалитьа я так сочинил, с удобствами )
Md = 1; Nd = 0; d=[]
x0 = x = int(input('введите натуральное число '))
while x != 1:
for i in range (2,x+1):
if (x % i) == 0:
Md = i; d += [i]; Nd += 1; x = int(x / i);
break
continue
if (Nd == 1) or (x0 ==1):
print('число ', x0, 'простое')
else:
print('Всего', Nd, 'делителей числа ', x0, ':', d, ' максимальный из них - ',Md)
Этот комментарий был удален автором.
ОтветитьУдалитьdef prime_factors_func():
ОтветитьУдалитьprime_factors = []
n = 600851475143
for i in range (2, n-1, 1):
if n % i == 0:
prime_factors.extend([i])
else:
continue
print(max(prime_factors))
prime_factors_func()
Единственное, что оооочень долго. Видимо, всё-таки не самая подходящая асимптотика. Но другие варианты в голов пока не приходя. Только перебором...
Только начинаю учить питон, не все знаю, но пытаюсь решать задачи, пока кажутся очень сложными))
ОтветитьУдалитьНад этой задачей думал больше всего, с час, дошел до такого решения:
n = 600851475143
for i in range(2, n + 1):
if n % i == 0:
flag = True
for i2 in range(2, i):
if i % i2 == 0:
flag = False
if flag == True:
print(i, end=' ')
Не понял как заставить программу запомнить все числа и выбрать максимальное, она просто выводит все простые делители числа по возрастанию, и последнее из них является максимальным, что есть ответ
Этот комментарий был удален автором.
ОтветитьУдалитьВашы варианты лаконичнее, но мой быстрее в 3 раза
ОтветитьУдалитьdef IsSimpleNumber(n):
for i in range(2, n):
if n % i == 0:
return False
break
else:
return True
def NextDiv(n):
i = 2
while i1:
if IsSimpleNumber(i):
print("Max simple divider: ",i)
break
i = NextDiv(i)
только начал изучение питона, не судите строго, у меня получилось так:
ОтветитьУдалитьn = 600851475143
i = 2
mx = 1
mn = 1
for i in range(i, n):
if n % i != 0:
i += 1
mn = i
else:
mx = n // mn
print(mx)
break
a = 60085147
ОтветитьУдалитьi = a // 2
while True:
if a % i == 0:
print(i)
break
i -= 1
Только код выполняется , очень долго)
Этот комментарий был удален автором.
ОтветитьУдалитьЭтот комментарий был удален автором.
ОтветитьУдалитьl = []
ОтветитьУдалитьa = 600851475143
for i in range(2, int(a**0.5)):
if a % i == 0:
l.append(i)
if a // i not in l:
l.append(a // i)
print(max(l))
Этот комментарий был удален автором.
ОтветитьУдалитьa = 600851475143
ОтветитьУдалитьb = []
c = 2
while a != 1 or a > c:
if a % c == 0:
a /= c
b.append(c)
c += 1
print (b[-1])
Переменная а - для заданного числа
Переменная с - для искомого делителя
Пустой список b - для сохранения найденных делителей
Создал цикл с условием крутить пока переменная а не будет ровна 1, или пока а не станет меньше с
Далее в цикле условие: если а делится на с без остатка, то поделить и перезаписать результат в переменную а и в список b добавить значение делителя. По завершению цикла print последнего элемента в списке
6857
Опрошу оценить мое решение на Python. Начал изучать недавно, надеюсь мое решение является правильным. ответ 6857
ОтветитьУдалитьx = 600851475143
for y in range(1, x):
if x % y == 0:
x = x / y
elif x == 1:
break
print(y)