Trouver un nombre premier dans le schéma en utilisant la récursion naturelle

Question

Je continue à brancher les exercices dans Comment concevoir des programmes par moi-même, mais j'ai réussi à rester coincé à nouveau. Cette fois, il est question 11.4.7:

développer la fonction est-non divisible par < = i. Il consomme un nombre naturel [> = 1], i, et un nombre naturel m, avecm. Si m n'est pas divisible par un nombre quelconque compris entre 1 (exclusif) et i (inclus), la fonction produit la valeur true; sinon, sa sortie est fausse.

utilisation est-not-divisible par < = i pour définir premier ?, qui consomme un nombre naturel et détermine si oui ou non il est premier.

La première partie, je n'ai pas eu trop de temps avec:

;; A natural number [>=1] is either 1. 1 or 
;; 2. (add1 n) where n is a natural number [>=1]. 

;; is-not-divisible-by<=i : N[>=1] N -> boolean 
(define (is-not-divisible-by<=i i m) 
    (cond 
    [(= i 1) true] 
    [else (cond 
      [(= (remainder m i) 0) false] 
      [else (is-not-divisible-by<=i (sub1 i) m)])])) 
(is-not-divisible-by<=i 3 6) ; expected: false. 
(is-not-divisible-by<=i 6 7) ; expected: true. 

Mais je ne vois pas comment je peux utiliser une variable pour le faire en utilisant la récursivité naturelle. J'ai pensé utiliser une liste, mais cela présente les mêmes problèmes.

La seule solution que je peux voir est de donner une autre variable - disons x - la même valeur que n, et puis de le faire de la manière est-not-divisible-par < = je le fais. Mais je pense que les auteurs ont l'intention de le faire d'une autre façon, plus simple. (Et je ne sais même pas comment faire ce que j'ai décrit de toute façon, haha.)

Ce problème a vraiment été busting mes fesses, donc toute aide ou des conseils, si vous pouviez, serait génial!

Answer 1

Un nombre premier est un nombre qui ne peut être divisé par un nombre inférieur à lui-même. Vous avez déjà mis en œuvre le « ne peut pas être divisé par un nombre plus petit que » partie:

(define (prime? n) 
    (is-not-divisible-by<=i (sub1 n) n)) 

Answer 2

(? Premier 1) obtient une erreur « division par zéro ».

Voici une version modifiée du code original. Il s'occupe du problème (prime? 1) pour l'instant.

(define (prime? p) 
    (define (non-divisible-by n d) 
    (cond 
    ((= d 1) #t) 
    (else (if(= (remainder n d) 0) 
      #f 
      (non-divisible-by n (- d 1)))))) 
    (if (= p 1) 
     #t 
     (non-divisible-by p (- p 1)))) 

maintenant (premier? 1) retourne #t

Answer 3

Il est pas nécessaire que vous diviser tous les nombres de n-1 à 2 à vérifier primalité. Vous avez seulement besoin de vérifier à partir de (étage (sqrt n)). Donc, une approche plus rapide (spécialement pour les grands nombres), qui prend également soin du problème indéfini (prime? 1), est:

(define (prime? n) 
    (is-not-divisible-by<=i (floor (sqrt n)) n))