מציאת מספרים ראשוניים Eratosthenes Algorithm

bennylisp, Racket, schemeLeave a Comment

מציאת מספרים ראשוניים scheme

הפונקציה מקבלת מספר שלם ומחזירה רשימה של כל המספרים הראשוניים עד לאותו מספר,

  • הפונקציה תחילה יוצרת רשימה מ 1 עד לאותו מספר באופן רקורסיבי על ידי קריאה לפונקציה createList 
  • הרשימה נשלחת לפונקציה נוספת erathosprimes1Help2   המקבלת רשימה ובכל מקום שהמספר אינו ראשוני המספר מוחלף ב f#
  • רשימה זו מועברת לפונקציה נוספת erathosprimes1Filter  שמוחקת את כל ה f# ומשאירה את המספרים הראשוניים בלבד

הקוד

(define(erathosprimes1 N)
  (if (inputCorrect2? N)
  (erathosprimes1Filter (erathosprimes1Help2 (createList 1 N) 2) )
  "error input"
  ))                                                                


(define(erathosprimes1Help L I K)
  (if (null? L) null
      (if (and(equal? (car L) #f)(= K I)) L
            (if (equal? K (+ I 1)) 
              (if (equal? (car L) #f) (cons (car L) (erathosprimes1Help (cdr L) I K))
                 (if (=(modulo (car L) I)0) (cons #f (erathosprimes1Help (cdr L) I K) ) 
         (cons (car L) (erathosprimes1Help (cdr L) I K)) )
     )
   (cons (car L) (erathosprimes1Help (cdr L) I (+ K 1))))
      )))


(define (erathosprimes1Help2 L I)
  (if (= (length L) (+ I 1)) L
        (erathosprimes1Help2 (erathosprimes1Help L I 1) (+ I 1))  )
      )


(define(erathosprimes1Filter L)
  (if (null? L) null
      (if (equal? (car L) #f) (erathosprimes1Filter (cdr L))
                  (cons (car L) (erathosprimes1Filter (cdr L))
                        ))))
      


(define(erathosprimes2Help L I K [RESULT null])
  (if (null? L) RESULT
      (if (and(equal? (car L) #f)(= K I)) RESULT
            (if (equal? K (+ I 1)) 
              (if (equal? (car L) #f) ( RESULT  (cons (car L) (erathosprimes1Help (cdr L) I K)RESULT))
                 (if (=(modulo (car L) I)0) (cons #f (erathosprimes1Help (cdr L) I K) ) 
         (cons (car L) (erathosprimes1Help (cdr L) I K)) )
     )
   (cons (car L) (erathosprimes1Help (cdr L) I (+ K 1))))
      )))



קרדיט: benny david from WS

כתיבת תגובה

האימייל לא יוצג באתר. שדות החובה מסומנים *