프라임 팩터가 너무 느리거나 충돌이 발생했습니다.

Question

현재 ProjectEuler 사이트의 일부 문제를 해결하여 LISP를 배우고 있습니다. 13,195있는 5, 7, 13, 29

번호 600851475143의 가장 큰 주요 요인은 무엇입니까의

소인수 : 문제 중 하나는이 요청?

이 작업을 수행하는 Lisp 코드를 함께 스크랩했습니다. 그러나 9 자리 이상의 숫자의 경우 매우 느립니다. 대부분의 경우 솔루션을 얻지 못했지만 8 자리 숫자는 약 4-5 초가 걸렸습니다. 더 많은 것은 인 무엇, 때때로 나는 "HEAP 초과했다"과실을 얻는다.

내 질문에 내가 코드를 실행하는 측면에서 뭔가 잘못하고 있는거야 (Aquamacs 사용)? 이 코드를 현재 작업에 더 잘 맞도록 최적화 할 수있는 방법은 무엇입니까? 더 중요한 것은, "초과 힙"충돌을 피할 수있는 방법은 무엇입니까?

코드 :

(defun potential-factors (number) 
    (loop for x from 1 to (ceiling (/ number 2)) 
     for y = x 
     collect y)) 

(defun factors (number) 
    (let (prime-factors '()) 
    (loop for x in (potential-factors number) 
      do (if (= (mod number x) 0) 
       (setq prime-factors (cons x prime-factors)))) 
    prime-factors)) 

(defun is-prime (n &optional (d (- n 1))) 
    (if (/= n 1) 
     (or (= d 1) 
      (and (/= (rem n d) 0) 
       (is-prime n (- d 1))))())) 

(defun problem-3 (number) 
    (last (sort (remove-if-not #'is-prime (factors number) :from-end t) #'<))) 

Answer 1

당신이 (potential-factors 600851475143)의 결과가 무엇이라고 생각합니까? 결과를 계산하는 데 얼마나 오래 걸릴 것이고 결과로 필요한 메모리는 얼마나 될까요?

Answer 2

potential-factors에 1에서 n/2 사이의 숫자 목록을 만드는 것이 문제입니다. 이 목록에는 엄청난 양의 메모리가 필요하며 프로그램이 중단됩니다. 좋은 소식은 이러한 숫자를 목록에 누적 할 필요는 없지만 한 번에 하나의 숫자 만 사용한다는 것입니다. factors에서 (loop for x in (potential-factors number)을 (loop for x from 1 to (ceiling (/ number 2))

으로 대체하십시오. 트릭을 수행해야합니다.

Answer 3

저는 수학자는 아니지만 또 다른 생각 : n을 2로 나눈 것에 대한 통찰력은 그 요소가 쌍으로 나타나는 것으로 보입니다. A는 A 시간 B가 N 일 때만 N의 요인이므로 B는 2 이상이어야합니다. 그러나 그 논리는 확장 될 수 있습니까? 3으로 나누는 것은 어떨까요? 3이 요인인지 확인한 후에는 1/3 N보다 큰 모든 숫자를 확인하는 것이 중요하지 않습니다. 4와 같은 경우 등이 있습니다. 관찰은 실제로 A가 B보다 작거나 같은 숫자 - 그래서 그 한계는 무엇입니까? A = B라면, A = B = A × A입니다.이 경우 A는 N의 제곱근을 의미합니다. 따라서 제곱근 N만큼만 검사하면됩니다. N/2까지 늘리지 말고.

하지만 저는 수학자가 아닙니다.