Самый большой простой коэффициент-Python

Question

Я пытаюсь найти самый большой простой коэффициент заданного числа (600851475143) с помощью Python. Я сделал следующий код, но я не знаю, что не так, и пользуюсь ли я правильным кодом. Помогите найти мою ошибку и улучшить ее.

import math 
def t(x): 

    l=[] 

    for i in range(1,int(math.sqrt(x))): 
     if x%i==0: 

      l.append(i) 
    return l 




def check(y): 
    for i in range(2,1+y/2): 
     if y%i==0: 
      return 'this is not prime' 
    return 'ya' 



print t(600851475143)  
print check(486847) 

Answer 1

Вы довольно близко. Ваш check() возвращается, прежде чем вы захотите его. Вы хотите:

def check(y): 
    for i in range(2,1+y/2): 
     if y%i==0: 
      return 'this is not prime' 
    return 'ya' 

Это будет ждать, пока вы не проверить все номера < y до возвращения ложными. Сейчас он проверяет 2, затем возвращает либо true, либо false.

Также t() возвращает все факторы, а не самый большой фактор. Для всего наибольшего фактора (предполагается, что есть один), вы хотите return l[-1]

EDIT: Хорошо, я думаю, что я получаю то, что вы собираетесь. С помощью этого t() и check(), вы можете получить наибольшее простое число от с:

def t(x): 
    l=[] 
    for i in range(1,int(math.sqrt(x))): 
     if x%i==0: 
      l.append(i) 
    return l 
    #Notice, return list of all factors 

def check(y): 
    for i in range(2,1+y/2): 
     if y%i==0: 
      return False 
    return True 

number_to_check = 92873465 
prime_factors = [] 
for factor in t(number_to_check): # Iterate through factors returned from t() 
    if check(factor): 
     prime_factors.append(factor) 

print "Largest Prime Factor: " + prime_factors[-1] 

Answer 2

Вы должны проверить, что все, что вы хотите добавить в список на самом деле является главным

for i in range(1,int(math.sqrt(x))): 
     if (x % i) != 0: 
      continue 
     if check(i): 
      l.append(i) 

Затем, поп последний (наибольший) элемент списка:

return l.pop() 

Вы также можете проверить до квадратного корня:

def check(y): 
    for i in range(2,int(math.sqrt(y))): 
     if (y % i) == 0: 
      return False 
    return True 

Вот слегка измененная версия, которая перебирает в обратном направлении (как это было предложено ПЗП), и возвращается, как только будет найдено простое:

#!/usr/bin/env python 
import math 
def t(x): 
    for i in xrange(int(math.sqrt(x)), 1, -1): 
     if (x % i) != 0: 
      continue 
     if check(i): 
      return i 
    return None 

def check(y): 
    for i in range(2, int(math.sqrt(y))): 
     if (y % i) == 0: 
      return False 
    return True 

print t(600851475143) 
print check(6857)