Каков самый большой делитель числа 600851475143 являющийся простым числом

Zlomorda

Для решения этой задачи я взял пример как разложить число на простые делители:

Возьмем заданной число и поделим его на два. Если делится без остатка — знат 2 простой делитель. Если не делится — знать делаем 2 + 1 и делим заданной число на 3.
После нахождения первого делителя, делим на него число из задачи и вписываем его на место оригинального числа.
Повторяем луп пока то число что мы проверяем не будет равно одному.
Выдаем это самое значение при котором проверочное число равно одному.

26 комментариев:

ода) казалось бы все так просто, но я бы фиг додумался

Почему тогда с число 1421 не работает?

неверно) есть делители больше

там else надо добавить перед count += 1, иначе программа будет криво работать

for i in range(1, num):
if (num % i == 0):
div.append(i)

этот код пайтон думает очень долго ��

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=' ')

Не понял как заставить программу запомнить все числа и выбрать максимальное, она просто выводит все простые делители числа по возрастанию, и последнее из них является максимальным, что есть ответ

a = 600851475143
l = []
i = 2
while i < a + 1:
if a % i == 0:
l.append(i)
a = a / i
i += 1
print(max(l))

Этот комментарий был удален автором.

Вашы варианты лаконичнее, но мой быстрее в 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

Только код выполняется , очень долго)

Этот комментарий был удален автором.

i = 600851475143
a = 2

while i != 1:
if i % a == 0:
i /= a
elif i % a != 0:
a += 1
print(a)

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)

Проект эйлера. Задача №3. Где ошибка?

У вас number в int не помещается. А вы цикл гоните от 2 до number. У вас условие i < number в цикле будет всегда выполнятся — потому что ну не может int i быть больше number.

edit: И вообще логика проверки на простоту у вас сломана. del = i выполнится для любого j, такого что i на него не делится. Т.е. если i=6, то при j=5 вы dеl перезапишите. Вам надо в цикле устанавливать bool flag. И, после цикла на него смотреть.

Facebook
Вконтакте
Twitter

til_down, Конечно, оно не справляется. Один только цикл до 600851475143 будет выполнятся минут 10. А там внутри ведь еще и цикл для проверки. Я думаю, ваше решение будет пару часов работать.

Однако, если вы будете сокращать number на i ( number /= i; ), пока оно делится (может, придется кучу раз сокращать), то не надо внутреннего цикла — i всегда будет простым.

Вторая оптимизация — можно остановиться, когда i*i > number. Тогда оставшееся number, если оно больше 1, будет каким-то простым числом.

Это все работает, потому что мы поддерживаем инвариант — number не делится ни на одно число, меньшее i (кроме 1, конечно). Поэтому надо циклом while сокращать i пока можно. Поэтому, если number делится на i, то i — простое. Ведь иначе был бы меньший i делитель number. Поэтому при i*i>number, number — простое, ведь иначе у него был бы какой-то делитель, меньший i.

Это решение будет работать сильно быстрее.

Wataru, большое спасибо! Решил использовать второй метод. Ответ вывел правильно.
Я решил разобраться, почему данный способ работает, но не смог понять. Потому как, работает он не для всех чисел. К примеру, если в качестве вводимого числа использовать 246 — программа выводит 3, хотя должна вывести 41.Можете объяснить почему?

И ещё, если есть возможность, можете написать(в виде кода) ваш способ решения —

Как найти наибольший простой делитель?

Каков самый большой делитель числа 600851475143, являющийся простым числом?

Необязательно писать ответ на определенном ЯП, просто непонятен алгоритм.

Ответы (3 шт):

Разобрался в данной задаче и хочу показать свою получившуюся программу, и может понятно объяснить принцип ее работы (она достаточно эффективна — без массивов и списков, содержит только один вложенный цикл и пару условий). Язык — Java.

И так. Так как нам нужно наибольший простой делитель, но пойдем сверху. И постепенно будет убавлять этот делитель на 1 до тех пор, пока не попадется нужный нам (это и есть первый цикл). Второй цикл вложен в первый и проверяет уже делители самого делителя числа (сложно, но здесь главное понять, дальше все легко).

Важной частью программы является счетчик (j). Он будет считать кол-во делителей у делителя числа. Если это число равно двум, значит оно является простым (а простое число делится только на 1 и на само себя) и оно нам подходит. Можно заканчивать программу и выводить число на экран.