ISPRIME 함수를 정의 할 때 문제가 발생했습니다.

Question

저는 LISP를 처음 접했고 초보자 문제를 겪고있었습니다. ISPRIME 함수를 정의하려고했지만 제대로 작동하지 않는 것 같습니다. 여기 내 코드입니다 :

(defun ISPRIME (n &optional (d (- n 1))) 
     (if (= d 0) 
      (return-from ISPRIME t)) 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) 
     (ISPRIME n (- d 1))) 

하지만 내 코드를 실행에 내가 예를 들어 값 5를 사용

(ISPRIME 5) 
Nil 

5는 소수해야한다. 나는 모든 것이 다음과 같다고 생각한다. (if (= (mod nd) 0) 문장은 그렇지 않아야한다 .d는 0에 도달 할 때까지 감소하고 true를 리턴 할 때까지 계속되어야한다. . 내 논리 오류가 발생하는 위치를

하나를 볼 수 있습니다 모든 도움에 감사드립니다

코드에 오류가 있습니다

Answer 1

! 어떤 수로 나누어 때문에 함수가 아니라 0, 1에서 중지해야이 1. 간단하게 기능을 변경이 방법입니다 :

(defun ISPRIME (n &optional (d (- n 1))) 
     (if (= d 1)       ; <- change from 0 to 1 
      (return-from ISPRIME t)) 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) 
     (ISPRIME n (- d 1))) 

그러나 함수가 재미의 마지막 호출에서 return-from 반환하기 때문에 매우 효율적이지 않다 있습니다

(defun isprime (n &optional (d (- n 1))) 
    (cond ((= d 1) t) 
     ((= (mod n d) 0) nil) 
     (t (isprime n (- d 1))))) 

: ction 특은 "재귀 타워"등 함수에서 대신 if의, cond 더 컴팩트 한 "조건"을 사용하여,이 방법으로 그것을 제거하고, 결과 return-from을 대체하여 다시 쓸 수 없습니다

이것은 여전히 ​​반복적이지만 Common Lisp에서는 더 관용적입니다. 물론보다 효율적인 반복 버전에서이 함수를 변형하고 더 많은 것을 적용 할 수 있습니다 efficient algorithm. 그러나 스마트 컴파일러는이 함수가 tail recursive이라는 사실 때문에이 함수를 반복하여 자동으로 변환합니다. 매개 변수 n이 1보다 크다는 것을

추가

또한 예를 들어, 초기 검사를 추가 할 수 있습니다 : 당신은 부울을 계산하기 때문에

(defun isprime (n &optional (d (- n 1))) 
    (cond ((<= n 1) nil) 
     ((= d 1) t) 
     ((= (mod n d) 0) nil) 
     (t (isprime n (- d 1))))) 

Answer 2

, (if test T NIL)의 인스턴스가 test로 대체 될 수있다 보다 일반적으로 결과는 아마도 하나의 부울 표현으로 표현 될 수 있습니다. 나는 그것들을 더 쉽게 읽을 수있는 경향이있다. 여기에 예제로 허용 대답의 약간의 수정이다

(defun is-prime (n) 
    (loop 
    for d = 2 then (+ d add) 
    for add = 1 then 2 
    thereis (> (* d d) n) 
    until (= (mod n d) 0))) 

그리고 이에 상응하는 DO 버전 :

(defun is-prime (n &optional (d (1- n))) 
    (or (= d 1) 
     (and (plusp d) 
      (plusp (mod n d)) 
      (is-prime n (1- d))))) 

완성도를 들어

, 윌 네스의 답변에 따라이 여기에 LOOP 버전입니다 : 커먼 리스프 더 tail call optimization 보증이 없기 때문에

(defun is-prime (n) 
    (do ((d 2 (+ d add)) 
     (add 1 2)) 
     ((> (* d d) n) t) 
    (when (zerop (mod n d)) 
     (return nil)))) 

Answer 3

당신은, (꼬리) 재귀를 사용할 수 없습니다. 대신 do 또는 loop을 사용하거나 prog과 go을 사용해도됩니다.

그리고 알고리즘, 이 부터 증가하는 순서에 항상 테스트 당신의 잠재적 인 약수, 당신은 (sqrt n) 초과하면 중지 :

(defun ISPRIME (n) 
    (prog ((d 2))       ; defines implicit block named NIL 
    LOOP 
     (if (> (* d d) n) 
      (return-from ISPRIME t)) ; (return T) also works 
     (if (= (mod n d) 0) 
      (return-from ISPRIME nil)) ; or just (return) 
     (if (= d 2) 
     (incf d 1) 
     (incf d 2)) 
     (go LOOP))) 

(return)입니다 (return nil) 및과 동일은 (return-from NIL val)과 같습니다. prog은 NIL이라는 암시 적 블록을 정의하므로 더 짧고 더 일반적으로 return을 대신 호출 할 수 있습니다.

여기 추구하는 재미 방법이 isprime 기능을 증가 수 공급을 필터링하여 생성 된 소수의 확장 목록을 사용하는 것입니다 만 이들에 의해 인수를 테스트 할 다른 isprime-p 기능의 약수 공급 장치로 사용되는 소수뿐 아니라 모든 확률이 아니라 다른 알고리즘 성능 향상을 달성 할 수 있습니다. 소수 목록은 필요에 따라 확장되어야합니다. 소수는 테스트 할 숫자의 제곱근까지만 올라갈 것이고, 소수는 최상위 프라임의 제곱근까지 숫자로 테스트해야합니다 (테스트 할 숫자의 네 번째 루트).