Project Euler Q # 3 Python

Question

Я действительно пытаюсь улучшить свои навыки математики/кодирования/решения проблем, работая над проблемами Project Euler, и я немного застрял в третьем вопросе. Вопрос: «Первыми факторами 13195 являются 5, 7, 13 и 29. Каков самый большой простой коэффициент числа 600851475143?»

И вот мой код до сих пор

import math 

def isPrime(n): 
    if n > 1: 
    for i in range(2, n): 
     if n % i == 0: 
      return False 
     else: 
      return True 
    else: 
    return False 

def highFactor(m): 
    factors = [] 
    for i in range(2, int(math.sqrt(m))): 
    if isPrime(i): 
     if m % i == 0: 
      factors.append(i) 
    print max(factors) 

highFactor(13195) 

Так что это, очевидно, испытывал на примере они дали, так как я уже знаю, что ответ должен быть 29, но когда я запускаю код дает мне 91. Что Я ошибаюсь?

Answer 1

Как указано в комментариях, ваша функция возвращает True слишком рано - например. если число не делится на 2, это не означает, что оно не будет делиться никаким более поздним числом в диапазоне (2, n) - рассмотрим 51 = 3 * 17 в качестве встречного примера.

Вот правильная версия вашего алгоритма:

def isPrime(n): 
    if n > 1: 
     for i in range(2, n): 
      if n % i == 0: 
       return False 
     return True 
    else: # if we have a negative number or 0 
     return False 

Как уже упоминалось другие, есть более быстрый способ проверить, является ли число простым; теперь ваша функция имеет сложность O(n), так как вы проверяете все числа до n; наблюдением, что n = sqrt(n) * sqrt(n) достаточно проверить до sqrt(n) + 1

def isPrime(n): 
    if n > 1: 
     for i in range(2, int(n ** 0.5) + 1): 
      if n % i == 0: 
       return False 
     return True 
    else: 
     return False 

Answer 2

Два вопроса:

(1) Ваша функция возвращает IsPrime Правда на первой итерации цикла. Вместо этого вы хотите закончить цикл, а затем вернуть True, если вы пережить весь цикл, не возвращая false.

(2) Возможно, что алгоритм будет иметь несколько копий одного и того же простого коэффициента (т. Е. 8 = 2 * 2 * 2). Вам было бы лучше установить m = m/i и перезапустить цикл каждый раз. Кроме того, вы, вероятно, хотите sqrt (m) +1, поскольку функция диапазона исключает верхний предел.

Answer 3

Как Остин прокомментировал isPrime возвращает истину слишком рано. При перемещении return True за пределами цикла for ваша функция проверит каждый номер в range(2, n), прежде чем подтвердить, что число является простым.

Допустим, вы должны были сделать isPrime(13), которые должны вернуть True

На первом проходе цикла if n % i == 0for будет if 13 % 2 == 0, который является ложным. Из-за else: return True в цикле for функция вернет True и прекратит работу.

Чтобы решить эту проблему можно было бы написать isPrime() как:

def isPrime(n): 
    if n > 1: 
     for i in range(2, n): 
      if n % i == 0: 
       return False 
     return True 
    else: 
     return False