Topic: -={ Challenge }=- is Prime

[Lee Mac]

The Challenge:

To construct a function to determine whether a natural number (positive integer) is prime.

Pour construire une fonction pour déterminer si un nombre naturel (entier positif) est premier.

Для построения функции определить, является ли натуральное число (целое положительное число) является простым.


Definition of a prime number:

A number only evenly divisible by itself and 1

Notes:

0 and 1 are not prime


To kick off:

Code: [Select]

(defun LM:Primep ( n )
  (and (/= n 1)
    (or (= n 2)
      (not
        (vl-some
          (function
            (lambda ( d ) (zerop (rem n d)))
          )
          (
            (lambda ( i r / l )
              (while (<= (setq i (+ 2 i)) r) (setq l (cons i l)))
              (cons 2 l)
            )
            1 (sqrt n)
          )
        )
      )
    )
  )
)

Enjoy!

[VovKa]

no Ukrainian translation, can't participate, sorry

[roy_043]

No new mathematical insights just a slightly different approach. On a number like 100000001 (can be divided by 17) my code is faster than Lee's. But on big numbers that are primes, like 1508138953, performance is similar.
Of course on even numbers my code wins hands down.

Code: [Select]

(defun kg:PrimeP (n / maxI i)
  (and
    (/= n 1)
    (or
      (= n 2)
      (and
        (/= (rem n 2) 0) ; check for even number
        (/= (setq maxI (sqrt n)) (fix maxI)) ; rare occurrence but you never know...
        (progn
          (setq i 1)
          (while (and (/= (rem n (setq i (+ i 2))) 0) (<= i maxI)))
          (/= (rem n i) 0)
        )
      )
    )
  )
)

[Lee Mac]

no Ukrainian translation, can't participate, sorry

Probably best that you don't - we'd have no chance 
 

[Lee Mac]

No new mathematical insights just a slightly different approach. On a number like 100000001 (can be divided by 17) my code is faster than Lee's. But on big numbers that are primes, like 1508138953, performance is similar.
Of course on even numbers my code wins hands down.

Nice coding Roy 

[Lee Mac]

Using theory that all integers can be represented in the form 6k+i for integer k, i=−1, 0, 1, 2, 3, 4 with 2 dividing (6k + 0), (6k + 2), (6k + 4) and 3 dividing (6k + 3)

Code: [Select]

(defun LM:Primep ( n / m u )
  (and (/= n 1)
    (or (= n 2) (= n 7)
      (not
        (or
          (zerop (rem n 2))
          (zerop (rem n 3))
          (zerop (rem (setq u (sqrt n)) 1))
          (progn
            (setq i 0.0)
            (while
              (and (<= (setq m (+ (* 6.0 (setq i (1+ i))) 1.0)) u)
                   (/= 0 (rem n m))
                   (/= 0 (rem n (- m 2.0)))
              )
            )
            (or (zerop (rem n m))
                (zerop (rem n (- m 2.0)))
            )
          )
        )
      )
    )
  )
)


[gile]

Hi,

Here's something I wrote sometimes ago, trying to make a function which 'learns'.
Rather than restart calculations from the first prime numbers, all 'knowed' prime numbers are stored in a list within the function.

Here's a 'demonstrative version'

Code: [Select]

(defun-q
  prime
  (num / lst den loop)
  (setq lst '(2 3))
  (if (and (= (type num) 'INT) (< 0 num))
    (if (or (member num lst) (= 1 num))
      (alert (strcat "I already know: " (itoa num) " is prime."))
      (if (< num (setq den (last lst)))
        (alert (strcat "I already know: " (itoa num) " is not prime."))
        (if (vl-some '(lambda (x) (zerop (rem num x))) lst)
          (alert (strcat "I calculated: " (itoa num) " is not prime."))
          (progn
            (setq loop   T
                  den (+ den 2)
            )
            (while (and loop (<= den num))
              (if (vl-some '(lambda (x) (zerop (rem den x))) lst)
                 (setq den (+ den 2))
                 (progn
                   (setq lst (append lst (list den)))
                   (alert (strcat "I learned a new prime number: "
                                  (itoa den)
                          )
                   )
                   (if (zerop (rem num den))
                     (if (= num den)
                       (alert (strcat "Now, I know "
                                      (itoa num)
                                      " is prime."
                              )
                       )
                       (progn
                         (alert (strcat "I calculated: "
                                        (itoa num)
                                        " is not prime."
                                )
                         )
                         (setq loop nil)
                       )
                     )
                     (setq den (+ den 2))
                   )
                 )
              )
            )
          )
        )
      )
    )
    (alert "Needs a strictly positive number")
  )
  (setq prime
         (cons (car prime)
               (cons (list 'setq 'lst (list 'quote lst))
                     (cddr prime)
               )
         )
  )
  (princ)
)
The same one with a boolean return.
(eval (cadr isPrime)) returns the list of the 'already knowed' prime numbers

Code: [Select]

(defun-q
  isPrime
  (num / lst den loop result)
  (setq lst '(2 3))
  (if (and (= (type num) 'INT) (< 0 num))
    (if (or (member num lst) (= 1 num))
      (setq result T)
      (if (<= (setq den (last lst)) num)
        (if (not (vl-some '(lambda (x) (zerop (rem num x))) lst))
          (progn
            (setq loop   T
                  den (+ den 2)
            )
            (while (and loop (<= den num))
              (if (vl-some '(lambda (x) (zerop (rem den x))) lst)
                 (setq den (+ den 2))
                 (progn
                   (setq lst (append lst (list den)))
                   (if (zerop (rem num den))
                     (if (= num den)
                       (setq result T)
                       (setq loop nil)
                     )
                     (setq den (+ den 2))
                   )
                 )
              )
            )
          )
        )
      )
    )
  )
  (setq isPrime
         (cons (car isPrime)
               (cons (list 'setq 'lst (list 'quote lst))
                     (cddr isPrime)
               )
         )
  )
  result
)

[VovKa]

Code: [Select]

(kg:PrimeP 3)
(LM:Primep 3)
(LM:Primep 5)


[qjchen]

Code: [Select]

;;;by qjchen@gmail.com
(defun is-prime(n)
 (defun find-2 (n i)
  (cond ((> (* i i) n) n)
        ((= (rem n i) 0) i)
        (T (find-2 n (1+ i)))
  )
 )
 (cond ((and (= (type n) 'INT) (> n 1)) (= (find-2 n 2) n))
       (T nil))
)

recently I also join a challenge here
http://bbs.mjtd.com/dispbbs.asp?boardid=37&Id=83019

there is also a is-prime question.

[Lee Mac]

Code: [Select]

(kg:PrimeP 3)
(LM:Primep 3)
(LM:Primep 5)


Ahhh!    How did i miss that 

[Lee Mac]

Same theory as above, but with modulo 12

Code: [Select]

(defun LM:Primep ( n / u m )
  (and (/= n 1)
    (or (member n '(2 3 5 7 11))
      (not
        (or
          (zerop (rem n 2))
          (zerop (rem n 3))
          (zerop (rem (setq u (sqrt n)) 1))
          (progn
            (setq i 0.0)
            (while
              (and
                (<= (setq m (+ (* 12.0 (setq i (1+ i))) 7.0)) u)
                (/= (rem n m) 0)
                (/= (rem n (- m 2)) 0)
                (/= (rem n (- m 6)) 0)
                (/= (rem n (- m 8)) 0)
              )
            )
            (vl-some (function (lambda ( x ) (zerop (rem n (- m x))))) '(0 2 6 8))
          )
        )
      )
    )
  )
)

[Lee Mac]

Hi,

Here's something I wrote sometimes ago, trying to make a function which 'learns'.
Rather than restart calculations from the first prime numbers, all 'knowed' prime numbers are stored in a list within the function.

Nice solution Gile - that is some great lateral thinking 

[roy_043]

Code: [Select]

(kg:PrimeP 3)
(LM:Primep 3)
(LM:Primep 5)


Code: [Select]

(kg:PrimeP 3) => nil
(LM:Primep 3) => T (first version of LM:Primep)
(LM:Primep 5) => T (first version of LM:Primep)
Well spotted VovKa!

[roy_043]

Code: [Select]

;;;by qjchen@gmail.com
(defun is-prime(n)
....


It's always nice to see (and try to understand ) a recursive function. But for very big numbers recursion is a problem:

Code: [Select]

(is-prime 1508138953) => error : LISP recursion stack limit exceeded

[LE3]

To construct a function to determine whether a natural number (positive integer) is prime.

Pour construire une fonction pour déterminer si un nombre naturel (entier positif) est premier.

Для построения функции определить, является ли натуральное число (целое положительное число) является простым.

Y Ahora? porque nada mas para los que hablen o entiendan esos idiomas....  

Buena onda eh!  

De todas maneras aqui esta una opcion:

Code: [Select]

static bool isPrime(int num)
{
if (num<=0 || num==1) return false;
for (int p=2; p<=num/2; p++) { if (num%p==0) return false; }
return true;
}