Topic: -={ Challenge }=- is Prime

[Lee Mac]

Luis, my C++ is muy rusty, but would this work?

Code: [Select]

#include <math.h>

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


[LE3]

On a first look and test - nope, it returns different values.

Also on this line:
for (int p=1; p<=sqrt(num); p+=2) { if (num%p==0) return false; }

Needs to be something like:
for (int p=1; p<=(int)sqrt((double)num); p+=2) { if (num%p==0) return false; }

Luis, my C++ is muy rusty, but would this work?

Code: [Select]

#include <math.h>

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


[Chuck Gabriel]

http://www.theswamp.org/index.php?topic=26363.msg318146#msg318146

[David Bethel]

Not real fancy, but should work:

Code: [Select]

(defun is_prime (i / r n)
  (setq n 3
        r (cond ((/= (type i) 'INT) T)
                ((<= i 1)           T)
                ((= i 2)          nil)
                ((zerop (rem i 2))  T)))
  (while (and (not r)
              (<= n (sqrt i)))
         (if (zerop (rem i n))
             (setq r T)
             (setq n (+ n 2))))
  (not r))

-David

Added 'INT and 2 test

[roy_043]

Code: [Select]

(is_prime 2)

[ElpanovEvgeniy]

my version:

Code: [Select]

(defun EE:Primep (n)
 (defun f (n i)
  (cond ((< i 2))
        ((= (rem n i) 0) nil)
        ((f n (1- i)))
  )
 )
 (and (> n 1) (f n (fix (sqrt n))))
)

[ElpanovEvgeniy]

version iteration

Code: [Select]

(defun EE:Primep_i (n / i)
 (setq i (fix (sqrt n)))
 (while (and (> i 1) (< 0 (rem n i)) (setq i (1- i))))
 (and (< i 2) (> n 1))
)

[Lee Mac]

The recursive function is most probably impractical as the stack limit will be hit quite easily for high primes, so the iterative version is preferable. But most are great examples (as usual )

Lee

[Lee Mac]

Perhaps a way to approach the problem is:

For testing a prime 'p'

** Choose a number 'x' with a large number of distinct prime factors

** Represent all integers modulo x

Hence for x=12 (2² x 3) we have 12k+i for integers k and i=0,1,2,3,4,5,6,7,8,9,10,11

** Check division of 'p' by prime factors of 'x'

Hence for x=12:

prime factor 2 we can remove i=0,2,4,6,8,10
prime factor 3 we can remove i=3,6,9

Hence we are left to check all integers of the form 12k+i <= sqrt(p)  for i=1,5,7,11

Severely reducing the number of division tests we have to make.

[Lee Mac]

Perhaps an example of such a function:

Code: [Select]

(defun LM:isPrime ( p / i k x )
  ;; © Lee Mac 2010
  (setq i (fix (sqrt p)) k 0)

  (if (< 1 p)
    (cond
      ( (vl-position p '(2 3 5 7 11)) T )
      ( (vl-some (function (lambda ( d ) (zerop (rem p d)))) '(2 3 5 7 11)) nil )
      ( (progn
          (while (and (<= (setq x (+ (* 12 (setq k (1+ k))) 11)) i)
                      (not (vl-some (function (lambda ( d ) (zerop (rem p d)))) (list x (- x 4) (- x 6) (- x 10))))))

          (> x i)
        )
      )
    )
  )
)


Code: [Select]

_$ (Benchmark '((LM:isPrime 123457) (EE:Primep_I 123457)))
Benchmarking ...............Elapsed milliseconds / relative speed for 4096 iteration(s):

    (LM:ISPRIME 123457)......1077 / 1.36 <fastest>
    (EE:PRIMEP_I 123457).....1467 / 1.00 <slowest>


[VovKa]

Code: [Select]

(LM:isPrime 1,2,25,35,49....)

[Lee Mac]

Code: [Select]

(LM:isPrime 1,2,25,35,49....)

Tweaked. 

[highflyingbird]

Code: [Select]

(defun HFB:isPrime (n / HD LG LH VA ret)
  (if (= (rem n 2) 0)
    nil
    (progn
      (setq hd 8
    lg 6
    lh 8
    va (1- n)
      )
      (setq ret t)
      (while (>= va hd)
(if (= (rem (- va hd) lg) 0)
  (setq ret nil
va hd
  )
)
(setq lh (+ lh 8)
      lg (+ lg 4)
      hd (+ hd lh)
)
      )
      ret
    )
  )
)
found some bug's in Lee's code.

Code: [Select]

(defun c:test(/ I J RANGE T0)

  (setq range (getreal "\nPlease enter a range(<100000000):"))
  (setq range (1- (fix range)))
  ;;Highflybird's
  (setq t0 (getvar "TDUSRTIMER"))
  (setq i 2)
  (setq j 1)    ;because 2 is a prime
  (repeat range
    (if (HFB:isprime i)
      (progn
        (setq j (1+ j))
        ;;(princ (strcat "\n" (itoa i)))
      )
    )
    (setq i (1+ i))
  )
  (princ "\nIt takes")
  (princ (* (- (getvar "TDUSRTIMER") t0) 86400))
  (princ "Second.")
  (princ (strcat "\nThe count of primes is:" (itoa j)))

  ;;Lee Mac's
  (setq t0 (getvar "TDUSRTIMER"))
  (setq i 2)
  (setq j 0)
  (repeat range
    (if (LM:isPrime i)
      (progn
        (setq j (1+ j))
        ;;(princ (strcat "\n" (itoa i)))
      )
    )
    (setq i (1+ i))
  )

  (princ "\nIt takes")
  (princ (* (- (getvar "TDUSRTIMER") t0) 86400))
  (princ "Second")
  (princ (strcat "\nThe count of primes is:" (itoa j)))
 
  (princ)
)

[highflyingbird]

for example:

Lee's  :
1000--------185        primes
10000------1284        primes

but actually:

1000--------168        primes
10000------1229        primes   

[David Bethel]

I came up with the same number of primes:

Command: iptest

Please enter a range(<100000000):1000

It takes0.016Second
The count of primes is:168

Command:
Command:
IPTEST
Please enter a range(<100000000):10000

It takes0.14Second
The count of primes is:1229

Command:
Command:
IPTEST
Please enter a range(<100000000):100000

It takes2.75Second
The count of primes is:9592

Command: