Text only | Text with Images

newLISP Fan Club

Forum => newLISP in the real world => Topic started by: cameyo on August 28, 2019, 07:14:43 AM

Title: Twin primes
Post by: cameyo on August 28, 2019, 07:14:43 AM
Two functions to calculate twin primes (pairs and pairs-i).
Code Select
(define (prime? n)
  (if (even? n) nil
      (= 1 (length (factor n)))))

(define (twin? n)
  (if (and (prime? n) (prime? (+ n 2)))
    (list n (+ n 2))
    nil))

(twin? 9)
;-> nil
(twin? 881)
;-> (881 883)

(define (pairs a b)
  (filter true? (map twin? (sequence a b))))

(pairs 3 1000)
;-> ((3 5) (5 7) (11 13) (17 19) (29 31) (41 43) (59 61) (71 73) (101 103) (107 109)
;->  (137 139) (149 151) (179 181) (191 193) (197 199) (227 229) (239 241) (269 271)
;->  (281 283) (311 313) (347 349) (419 421) (431 433) (461 463) (521 523) (569 571)
;->  (599 601) (617 619) (641 643) (659 661) (809 811) (821 823) (827 829) (857 859)
;->  (881 883))
(length (pairs 3 1000))
;-> 35
(time (pairs 3 2e7))
;-> 47479.457

==================================================

(define (pairs-i a b)
  (local (idx found out)
    (setq found nil)
    (setq idx a)
    ; only the number 5 belongs to two pairs of twin prime numbers
    (setq out '((3 5) (5 7)))
    (while (< idx b)
      (if (and (prime? idx) (prime? (+ idx 2)))
        (begin
        (push (list idx (+ idx 2)) out -1)
        (setq found true))
      )
      (if found (++ idx 4) (++ idx 2))
      (setq found nil)
    )
    out
  )
)

(pairs-i 7 1000)
;-> ((3 5) (5 7) (11 13) (17 19) (29 31) (41 43) (59 61) (71 73) (101 103) (107 109)
;->  (137 139) (149 151) (179 181) (191 193) (197 199) (227 229) (239 241) (269 271)
;->  (281 283) (311 313) (347 349) (419 421) (431 433) (461 463) (521 523) (569 571)
;->  (599 601) (617 619) (641 643) (659 661) (809 811) (821 823) (827 829) (857 859)
;->  (881 883))
(length (pairs-i 7 1000))
;-> 35
(time (pairs-i 7 2e7))
;-> 43177.908
Post yours :-)
Title: Re: Twin primes
Post by: rrq on August 30, 2019, 12:11:24 AM
Something like this, perhaps:
Code Select
(define (pairs-i a b)
  (let ((out (list)) (x nil))
    (for (y (if (odd? a) a (inc a)) b 2)
      (if (1 (factor y)) (setf y nil) x (push (list x y) out -1))
      (setf x y))
    out))
Title: Re: Twin primes
Post by: cameyo on August 30, 2019, 01:18:29 AM
Thanks ralph.ronnquist. This is faster than mine :-)

Have a nice day.
Title: Re: Twin primes
Post by: rrq on August 31, 2019, 06:35:39 PM
You will gain a bit in speed for handling larger numbers by checking if the modulus of a prime product include any of the product primes. The code could be something like the following:
Code Select
(define (pairs-i1 a b)
  (let ((out (list)) (x nil) (FX (* 2 3 5 7 11 13)) (M 0))
    (for (y (if (odd? a) a (inc a)) b 2)
      (if (if (< y FX) (1 (factor y))
             (or (= (setf M (% y FX))) (if (factor M) (<= ($it 0) 13)) (1 (factor y))))
        (setf y nil)
        x (push (list x y) out -1))
      (setf x y))
    out))
That example uses the prime product (* 2 3 5 7 11 13). For numbers greater than that, it checks if the modulus is a product of any of those primes, in which case the number as whole is divisible by that prime (and therefore not a prime itself). Notably, the factorization of the modulus is typically faster, and the end result is a faster filtering out of these. The speed up for handling large numbers is significant (~30%).
Text only | Text with Images