ded-Egor / euler03
Clone via HTTPS Clone with Git or checkout with SVN using the repository’s web address.
Learn more about clone URLs
Проект Эйлера. Задача 3. Python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
| #Простые делители числа 13195 — это 5, 7, 13 и 29. |
| #Каков самый большой делитель числа 600851475143, являющийся простым числом? |
| # Ответ: 6857 |
| num=600851475143 |
| count=1 |
| while num!=1: |
| count+=1 |
| if num%count==0: |
| num/=count |
| print(count) |
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Zlomorda
Для решения этой задачи я взял пример как разложить число на простые делители:
И исходя из этого примера и написал алгоритм по нахождению самого большого делителя.
num = 600851475143 count = 2 while 1: if num % count == 0: num /= count if num == 1: print(count) break count += 1
- Возьмем заданной число и поделим его на два. Если делится без остатка — знат 2 простой делитель. Если не делится — знать делаем 2 + 1 и делим заданной число на 3.
- После нахождения первого делителя, делим на него число из задачи и вписываем его на место оригинального числа.
- Повторяем луп пока то число что мы проверяем не будет равно одному.
- Выдаем это самое значение при котором проверочное число равно одному.
24 комментария:
ода) казалось бы все так просто, но я бы фиг додумался Ответить Удалить
Почему тогда с число 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=’ ‘)
Не понял как заставить программу запомнить все числа и выбрать максимальное, она просто выводит все простые делители числа по возрастанию, и последнее из них является максимальным, что есть ответ Ответить Удалить
Этот комментарий был удален автором. Ответить Удалить
Вашы варианты лаконичнее, но мой быстрее в 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)
Ответить Удалить
Задача №3 Наибольший простой делитель
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Решение задачи от разработчиков на Python:
Copy to Clipboard
Еще одно решение задачи на Python:
Copy to Clipboard
Еще одно решение задачи на Python:
Copy to Clipboard
Решение с помощью факторизации:
Copy to Clipboard
Еще одно простое решение:
Простое число — это натуральное число больше единицы, которое делится на 1 и само на себя. Чтобы найти все простые делители разумно будет сократить диапазон значений для перебора, поэтому будем перебирать до квадратного корня 600851475143 округленного вверх (функцией math.ceil)
Перебор будем вести начиная с числа 3.
Если i делит число на цело, рекурсивно обращаемся к функции issimple c аргументом i.
Функция issimple возвращает пустой список если число является простым. В этом случае число попадает в результирующий список.
Далее остается только вернуть максимальное значение массива простых чисел, которые нацело делят число 600851475143
Copy to Clipboard
Понравилось решение? Поделись своей реализацией в комментариях! ��
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Каков самый большой делитель числа 600851475143, являющийся простым числом?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
x = 0 num = 600851475143 sp = [] n = num def pr(n): for x in range(2, n - 1): if not n % x == 0 or n == 1: return True else: return False for i in range(1, num): if pr(i) == True and n % i == 0: sp.append(i) n = num / i if n == 1: break print(max(sp))
Помогите понять, что заставляет программу работать бесконечно долго. Функцию создал, что бы понять простое число или нет. Цикл для перебора простых делителей числа. Не знаю что мешает программе работать корректно.
Лучшие ответы ( 2 )
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
Ответы с готовыми решениями:
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Простые делители числа 13195 — это 5, 7, 13 и 29. Каков самый большой делитель числа.
Каков самый большой делитель числа 600851475143, являющийся простым числом
Простые делители числа 13195 — это 5, 7, 13 и 29. Каков самый большой делитель числа 600851475143.
Каков самый большой делитель числа 600851475143, являющийся простым числом?
Товарищи, помогайте, потому что у меня сейчас случится дикий приступ. Вообщем, задача такая: Каков.
Самый большой делитель сложного числа, являющийся простым числом
Простые делители числа 13195 — это 5, 7, 13 и 29. Какой самый большой делитель числа.
Найти в данной последовательности число, которое имеет самый большой наибольший общий делитель с числом А
Дана последовательность из N натуральных чисел и натуральное число А. Найти в данной.
290 / 130 / 58
Регистрация: 24.11.2019
Сообщений: 532
Все работает, но очень медленно. Вам бы над алгоритмом поработать.
Добавлено через 1 минуту
Сообщение от Tamplier22 
for i in range(1, num):
for i in range(1, num+1):
3973 / 2882 / 672
Регистрация: 08.06.2007
Сообщений: 9,709
Записей в блоге: 4
1 2 3 4 5 6 7 8
num = 600851475143 d = 2 while num != 1 and d*d num: if num % d == 0: num //= d else: d += 1 print(num)
Добавлено через 8 минут
Сообщение от palva
while num != 1 and d*d num:
Здесь избыточное условие. Достаточно
while d*d num:
306 / 287 / 116
Регистрация: 23.01.2018
Сообщений: 933
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
def divisors(n): yield 1 i = 2 while i**2 n: if n % i == 0: yield i j = n // i if j != i: yield j i += 1 def prime(n): if n 2: return False if n % 2 == 0: return n == 2 if n % 3 == 0: return n == 3 i, s = 5, 2 while i**2 n: if n % i == 0: return False i += s s = 4 if s == 2 else 2 return True print(max(i for i in divisors(600851475143) if prime(i)))
35367 / 19966 / 4181
Регистрация: 12.02.2012
Сообщений: 33,130
Записей в блоге: 13
Сообщение было отмечено mik-a-el как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
def isPrime(n): i=2 while(i*in): if n%i==0: return False return True #n=600851475143 def max_prime_div(n): k=3 while(True): if n%k==0: r=n//k if isPrime(r): return r k+=2 print(max_prime_div(600851475143))
306 / 287 / 116
Регистрация: 23.01.2018
Сообщений: 933
Сообщение было отмечено mik-a-el как решение
Решение
1 2 3 4 5 6 7 8 9 10 11 12 13 14
from math import sqrt n = 600851475143 i = 2 while n % i != 0 or any(n // i % j == 0 for j in range(2, int(sqrt(n // i))+1)): if i == 2: i = 3 elif i == 3: i = 5 else: i += (9 - i % 6) // 2 print(n // i)
Регистрация: 03.09.2020
Сообщений: 1
1 2 3 4 5 6 7 8 9
num = 600851475143 d = 2 while num != 1 and d*d num: if num % d == 0: num //= d else: d += 1 print(num) # Используется свойство числа , макс. делитель меньше или равен квадратному корню числа
Регистрация: 09.01.2022
Сообщений: 1
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
''' Делается с помощью 2 методов первый просто проверяет число на простату) второй ищет самый больший делитель при условии что ] максимально допустимый делитель меньше или равен квадратному корню числа(с округлением) [given_number ** (0.5)] ''' def prime_number(number: int): a = number k = 0 for i in range(2, a // 2 + 1): if (a % i == 0): k = k + 1 if (k 0): return True def high_prime_number_division(given_number: int): list_num = [] for element in range(2, given_number): if element round(given_number ** (0.5)): if given_number%element==0: if prime_number(element): list_num.append(element) else: return list_num[-1] print(high_prime_number_division(600851475143))