저는 현재 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
[Sieve 알고리즘] (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) 이것은 Projecteuler와 다른 많은 사람들의 도전에 생명을 구할 것입니다. 어려운 일이라면'시브 (Sieve) 알고리즘 '을 사용하여이 질문에 대한 답을 게시 할 수 있습니다. 그렇지 않으면 자신과 함께 시도해보십시오. 이것이 최선의 방법입니다. 또한, 한 가지 기억하십시오 : Projecteuler의 질문은 1 분 이내에 해결되어야합니다. 그렇지 않은 경우, 접근 방식/알고리즘/사고 방식을 변경해야합니다. –
@ChehebNexus 체는 좋지만 다른 접근 방식을 구현하지 않은 이유를 이해하는 것이 더 좋습니다. 또한 오일러 문제의 프로젝트 시간 제한도 없습니다. 무차별 대입 방식을 사용하고 싶다면 왜 안 되겠습니까? – njzk2
@ njzk2 네, 여기 요점이 있습니다. –