Следующий код вычисляет наибольший простой множитель данного числа. Это решение проблемы номер 3 в Project Euler.
import math
def is_prime(n):
for i in range(2,int(math.sqrt(n))):
if n%i==0:
return False
return True
prime_factors =[]
n=600851475143
for i in range(1,int((math.sqrt(n)))):
if n%i==0:
if is_prime(i):
prime_factors.append(i)
print(max(prime_factors))
Моя оценка Первый для l oop работает от 1 до sqrt (n). Для каждого элемента в этом l oop метод is_prime запускает a для l oop от 1 до sqrt (i). Таким образом, время выполнения будет O (n ^ 1/2 * n ^ 1/4), т. Е. O (n ^ 3/4). Пожалуйста, поправьте меня, если я ошибаюсь.