왜 이것이 소수의 소수를 통과하게합니까?

Question

Project Euler 질문으로 돌아가서 코드 속도를 높일 수 있는지 알아 보려면 003 : 정말 큰 숫자의 최대 소수점 찾기.

def is_prime(n): 
    '''check if n is prime''' 
    if n == 1: return 0 
    elif n == 2: return 1 
    elif n % 2 == 0: return 0 

    for i in range(3, int(n**0.5) +1, 2): 
     if n % i == 0: 
      return 0 
    else: 
     return 1 

factor_list = [] 
the_number = 600851475143 
for i in range(3, int(the_number**0.5) +1, 2): 
    if the_number % i == 0: factor_list.append(i) 

print factor_list 
for i in factor_list: 
    if is_prime(i) == False: factor_list.remove(i) 

print factor_list 
print max(factor_list) 

첫 번째 인쇄 호출 인쇄 : [71, 839, 1471, 6857, 59569, 104441, 486847] 지금까지 N의 사전 N^0.5 요인을 인쇄, 너무 좋아.

두 번째 인쇄 호출이 인쇄됩니다. [71, 839, 1471, 6857, 104441] 잠깐, 어떻게 104441이 is_prime 함수를 통과 했습니까?

세 번째 인쇄 호출은 잘못된 대답, 즉 104441을 인쇄합니다. 제 질문은 어떻게 104441이 미끄러 져 나오는지입니다.

Answer 1

for 루프에 문제가 있다고 생각합니다. for-each 루프를 사용할 때 값을 건너 뛰기 때문에 일반적으로 값을 제거하지 않으려 고합니다. 그래서 무슨 일이 일어 났는지는 59569이 제거되고 그 다음 제거하기 때문에 다음 i 값은 486847입니다.

해결 방법을 원한다면 steveha의 코드를 참조하십시오.

Answer 2

반복하면서 목록을 수정하려고하면 항상 힘들습니다. 필요하지 않은 값을 추출하는 대신 필요한 목록을 만드는 것이 더 낫고 안전합니다.

이 코드

완벽하게 작동합니다 : 또한

factor_list = [n for n in xrange(3, int(the_number**0.5) +1, 2) if the_number % n == 0] 
print(factor_list) 

prime_factors = [n for n in factor_list if is_prime(n)] 
print(prime_factors) 

answer = max(prime_factors) 
print(answer) 

, 당신은 is_prime()하지 0 및 1에서 False 및 True를 반환해야합니다.