2017-05-06 14 views
3

저는 현재 Project Euler를 통해 작업하고 있습니다.이 문제는 문제 3의 파이썬에서의 시도였습니다.이 작업을 실행하여 약 30 분을 보냈습니다. 이 후, 나는 "sum"아래의 숫자를 보았다. 나는 몇 가지 문제점을 발견했다 :이 숫자 중 일부는 고르고 소수이므로 일부 숫자는 n의 적절한 인자가 아니었다. 허락하면 그들은 0.000001 (대개 x.99999230984 또는 그 이상이 나왔다.)에 의해서만 벗어났다. 내가 결국 들렀던 수는 3145819243.0이었다.이것이 왜 Fermat 's Factorization의 잘못된 구현입니까?

누구든지 이러한 오류가 발생하는 이유를 설명 할 수 있습니까?

EDIT : 기본적으로 정리하면 변수의 재 배열을 통해 n + y^2의 제곱근을 사용하여 x를 풀 수 있고, y는 정수가 될 때까지 bruteforced가됩니다. 이 후에 실제 소수 요소는 x + y가됩니다.

여기 내 코드입니다.

import math 
n = int(600851475143) 
y = int(1) 
while y >= 1: 
    if math.sqrt(n + (y**2)).is_integer(): 
     x = math.sqrt(n + (y**2)) 
     print "x" 
     print x 
     print "sum" 
     print x + y 
     if x + y > (600851475142/2): 
      print "dead" 
     else: 
      print "nvm" 
    y = y + 1 
+0

[Sieve 알고리즘] (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 이것은 Projecteuler와 다른 많은 사람들의 도전에 생명을 구할 것입니다. 어려운 일이라면'시브 (Sieve) 알고리즘 '을 사용하여이 질문에 대한 답을 게시 할 수 있습니다. 그렇지 않으면 자신과 함께 시도해보십시오. 이것이 최선의 방법입니다. 또한, 한 가지 기억하십시오 : Projecteuler의 질문은 1 분 이내에 해결되어야합니다. 그렇지 않은 경우, 접근 방식/알고리즘/사고 방식을 변경해야합니다. –

+1

@ChehebNexus 체는 좋지만 다른 접근 방식을 구현하지 않은 이유를 이해하는 것이 더 좋습니다. 또한 오일러 문제의 프로젝트 시간 제한도 없습니다. 무차별 대입 방식을 사용하고 싶다면 왜 안 되겠습니까? – njzk2

+0

@ njzk2 네, 여기 요점이 있습니다. –

답변

4

큰 숫자와 부동 소수점 정밀도의 일반적인 문제.

y = 323734167에 도달하면 math.sqrt(n + y**2)math.sqrt(104804411734659032)입니다.

이것은 울프 램 알파에 따르면 3.23735095000000010811308548429078847808587868214170702... × 10^8 즉 정수가 아니지만 파이썬에 따르면 323735095.0입니다.

파이썬은 .00000001...을 볼 수있는 정밀도가 없습니다. 대신 테스트 is_integer

, 당신은 결과의 제곱 테스트 할 수 있습니다

> 323735095 ** 2 
=> 104804411734659025 

을하고 입력을 (그렇지, 입력이 7로 떨어져, 104804411734659032입니다 않음)과 일치하는 경우를 참조하십시오.

+0

오, 오케이. 그 외의 구현은 정확합니까? –

+0

최적화 할 여지가 있지만, fermat의 인수 분해를 올바르게 구현 한 것처럼 보입니다. 그래도 더 나은 제곱근을 찾아야합니다. – njzk2

+0

(http://stackoverflow.com/questions/30490439/how-to-take-square-root-of-large-numbers-in-python 참조) – njzk2