المساعدة في فهم غربال تنفيذ eratosthenes

Question

هذا ممل ، وأنا أعلم ، لكنني بحاجة إلى القليل من المساعدة في فهم تنفيذ غربال الإيراتوستين. إنه الحل مشكلة برمجة البرمجة هذه.

(define (primes n)
  (let* ((max-index (quotient (- n 3) 2))
         (v (make-vector (+ 1 max-index) #t)))
    (let loop ((i 0) (ps '(2)))
      (let ((p (+ i i 3)) (startj (+ (* 2 i i) (* 6 i) 3)))
        (cond ((>= (* p p) n)
               (let loop ((j i) (ps ps))
                  (cond ((> j max-index) (reverse ps))
                        ((vector-ref v j)
                          (loop (+ j 1) (cons (+ j j 3) ps)))
                        (else (loop (+ j 1) ps)))))
              ((vector-ref v i)
                (let loop ((j startj))
                  (if (<= j max-index)
                      (begin (vector-set! v j #f)
                             (loop (+ j p)))))
                      (loop (+ 1 i) (cons p ps)))
              (else (loop (+ 1 i) ps)))))))

الجزء الذي أواجه مشكلة مع startj. الآن ، أستطيع أن أرى ذلك p سيتم ركوب الدراجات من خلال الأرقام الفردية التي تبدأ من 3 ، والتي تم تعريفها على أنها (+ i i 3). لكني لا أفهم العلاقة بين p و startj, ، الذي (+ (* 2 i i) (* 6 i) 3).

---

تعديل: أنا أفهم أن الفكرة هي تخطي الأرقام التي سبق انخلاقها. ينص تعريف اللغز على أنه عند غربلة رقم x, ، يجب أن يبدأ غربلة مربع x. لذلك ، عند غربلة 3 ، ابدأ بالتخلص من 9 ، إلخ.

ومع ذلك ، ما لا أفهمه هو كيف توصل المؤلف إلى هذا التعبير startj (من الناحية الجبرية).

من تعليقات اللغز:

بشكل عام ، عند غربلة N ، يبدأ غربلة N-squared لأن جميع المضاعفات السابقة لـ N قد تم بالفعل غلقها.

يرتبط بقية التعبير مع المرجع المتبادل بين الأرقام وفهارس الغربال. هناك 2 في التعبير لأننا ألغنا جميع الأرقام الزوجية قبل أن نبدأ من أي وقت مضى. هناك 3 في التعبير لأن ناقلات المخطط لا تعتمد على الصفر ، والأرقام 0 و 1 و 2 ليست جزءًا من الغربال. أعتقد أن 6 في الواقع مزيج من 2 و 3 ، ولكن لقد مر بعض الوقت منذ أن نظرت إلى الكود ، لذلك سأتركه لك لمعرفة ذلك.

---

إذا كان بإمكان أي شخص مساعدتي في هذا ، فسيكون ذلك رائعًا. شكرًا!

Answer 1

أعتقد أنني اكتشفت ذلك ، بمساعدة البرمجة " تعليقات على موقعه على الويب.

لإعادة صياغة المشكلة ، startj تم تعريفه في القائمة باسم (+ (* 2 i i) (* 6 i) 3), ، بمعنى آخر 2i^2 + 6i + 3.

لم أفهم في البداية كيف يتعلق هذا التعبير p - منذ "غربلة" لعدد p يجب أن تبدأ في p^2, ، تصورت ذلك startj يجب أن يكون شيئًا يتعلق 4i^2 + 12i + 9.

لكن، startj هو فهرس في المتجه v, الذي يحتوي على أرقام غريبة تبدأ من 3. ، الفهرس ل p^2 هو في الواقع (p^2 - 3) / 2.

توسيع المعادلة: (p^2 - 3) / 2 = ([4i^2 + 12i + 9] - 3) / 2 = 2i^2 + 6i + 3 - وهي قيمة startj.

أشعر أنه قد يكون من الواضح أن تحدد startj مثل (quotient (- (* p p) 3) 2), ، ولكن على أي حال - أعتقد أن هذا يحلها :)

Answer 2

ديفيد سيلر: ربما ليس أوضح ، ولكن بالإضافة إلى تنفيذ الغربال الأساسي ، يتعين عليه أيضًا تنفيذ التحسينات الثلاثة الموضحة في التمرين.

هارتو: كان هذا التمرين الثاني. كنت لا أزال أجرب أسلوب الكتابة الخاص بي.

الفتحة: صحيح.

شاهد تفسيرًا أكثر اكتمالًا في تعليقي في برمجة البراكسي.

تعديل: لقد أضفت تعليقًا إضافيًا في برمجة Praxis. وعندما نظرت بالفعل إلى الكود ، كنت مخطئًا في اشتقاق الرقم 6 في الصيغة ؛ آسف أنا ضللك.