Topic: -={ Challenge }=- is Prime

[Lee Mac]

Looks like I'm going to have to take another look at my code 

[Lee Mac]

Code: [Select]

(HFB:isPrime 2)


Code: [Select]

(HFB:isPrime 1)


[Lee Mac]

Hopefully better 

Code: [Select]

(defun LM:isPrime ( p / i r f )
  ;; © Lee Mac 2010
  (if (or (= 2 p) (= 3 p)) T
    (progn
      (setq i (fix (sqrt p))
            r (or (> 2 p) (zerop (rem p 2)) (zerop (rem p 3))) f -1)

      (while (and (not r) (<= (setq f (+ f 6)) i))
        (if (or (zerop (rem p f)) (zerop (rem p (+ f 2))))
          (setq r T)
        )
      )

      (not r)
    )
  )
)
Liked your loop control David

[Lee Mac]

Provided there aren't bugs (highly possible!)

Please enter a range(<100000000):1000

---- HFB ----
It takes 0.007 Seconds
The count of primes is: 168

---- DB ----
It takes 0.01 Seconds
The count of primes is: 168

---- LM -----
It takes 0.006 Seconds
The count of primes is: 168

Please enter a range(<100000000):10000

---- HFB ----
It takes 0.281 Seconds
The count of primes is: 1229

---- DB ----
It takes 0.34 Seconds
The count of primes is: 1229

---- LM -----
It takes 0.21 Seconds
The count of primes is: 1229

Please enter a range(<100000000):100000

---- HFB ----
It takes 6.783 Seconds
The count of primes is: 9592

---- DB ----
It takes 6.639 Seconds
The count of primes is: 9592

---- LM -----
It takes 3.436 Seconds
The count of primes is: 9592

[David Bethel]

Code: [Select]


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

Surprised me how much faster it is when you don't use the (sqrt) function each iteneration  -David

[Lee Mac]

Certainly improves the time David, the less calculated within the loop the better 

Please enter a range(<100000000):1000

---- HFB ----
It takes 0.007 Seconds
The count of primes is: 168

---- DB ----
It takes 0.016 Seconds
The count of primes is: 168

---- LM -----
It takes 0.013 Seconds
The count of primes is: 168

Please enter a range(<100000000):10000

---- HFB ----
It takes 0.184 Seconds
The count of primes is: 1229

---- DB ----
It takes 0.228 Seconds
The count of primes is: 1229

---- LM -----
It takes 0.147 Seconds
The count of primes is: 1229

Please enter a range(<100000000):100000

---- HFB ----
It takes 6.322 Seconds
The count of primes is: 9592

---- DB ----
It takes 5.37 Seconds
The count of primes is: 9592

---- LM -----
It takes 3.316 Seconds
The count of primes is: 9592

Please enter a range(<100000000):200000

---- HFB ----
It takes 18.25 Seconds
The count of primes is: 17984

---- DB ----
It takes 15.028 Seconds
The count of primes is: 17984

---- LM -----
It takes 8.587 Seconds
The count of primes is: 17984

[pkohut]

A dollar short and a day late. Was in Python so...

Code: [Select]

def PrintIsPrime(x):
"""Determines if x is prime and prints result"""
s1 = "Is prime!"
s2 = "Is not prime!"

if x < 2 or (x > 2 and x % 2 == 0):
s = s2
elif x == 2:
s = s1
else:
i = 3
while x % i != 0:
i += 2
s = s1 if i == x else s2
print(x, s)

def IsPrime(x):
"""Returns True/False result of x == prime number"""
if x < 2 or (x > 2 and x % 2 == 0):
return False
elif x == 2:
return True
else:
i = 3
while x % i != 0:
i += 2
return True if i == x else False


>>> PrintIsPrime(3)
3 Is prime!
>>> PrintIsPrime(101)
101 Is prime!
>>> PrintIsPrime(100000001)
100000001 Is not prime!
>>> IsPrime(1508138953)
1508138953 Is prime!  <<<<-------That one took a minute or so to calc.

>>> IsPrime(3)
True
>>> IsPrime(3)
True
>>> IsPrime(21)
False
>>> IsPrime(31)
True

[highflyingbird]

How about" Miller-Rabin primality test"?
when the number < 3.4X10^14 ,the result of test is correct.

Code: [Select]

static unsigned g_aPrimeList[] = { // 100素数表
        2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
};
unsigned Montgomery(INT64 n,unsigned p,unsigned m)
{ //快速计算(n^e)%m的值
unsigned k=1;
n%=m;
while(p!=1)
{
if(0!=(p&1))
k=(k*n)%m;
n=(n*n)%m;
p>>=1;
}
return(n*k)%m;
}

bool RabbinMillerTest( unsigned n )
{
if (n<2)
{ // 小于2的数即不是合数也不是素数
throw 0;
}

const unsigned nPrimeListSize=sizeof(g_aPrimeList)/sizeof(unsigned);//求素数表元素个数
for(int i=0;i<nPrimeListSize;++i)
{// 按照素数表中的数对当前素数进行判断
if (n/2+1<=g_aPrimeList[i])
{// 如果已经小于当前素数表的数，则一定是素数
return true;
}
if (0==n%g_aPrimeList[i])
{// 余数为0则说明一定不是素数
return false;
}
}
// 找到r和m，使得n = 2^r * m + 1;
int r = 0, m = n - 1; // ( n - 1 ) 一定是合数
while ( 0 == ( m & 1 ) )
{
m >>= 1; // 右移一位
r++; // 统计右移的次数
}
const unsigned nTestCnt = 7; // 表示进行测试的次数
for ( unsigned i = 0; i < nTestCnt; ++i )
{ // 利用随机数进行测试，
int a = g_aPrimeList[ i ];
if ( 1 != Montgomery( a, m, n ) )
{
int j = 0;
int e = 1;
for ( ; j < r; ++j )
{
if ( n - 1 == Montgomery( a, m * e, n ) )
{
break;
}
e <<= 1;
}
if (j == r)
{
return false;
}
}
}
return true;
}

RabbinMillerTest (2234223321);
return 0;

because this way used "_int64",so it's not  applicable for LISP . but for a small number ,it's ok.

Code: [Select]


(defun paw_mod( bs power diver)
  (cond
    ((zerop power)
     1
    )
    ((= power 1)
     bs
    )
    ((= (logand power 1) 0)
     (paw_mod (rem (* bs bs) diver) (lsh power -1) diver)
    )
    (t
      (rem (* (paw_mod (rem (* bs bs) diver) (/ power 2) diver) bs) diver)
    )
  )
)

(defun RabbinMiller (base num / D K N RET TT)
  (setq n (1- num))
  (setq d n)
  (while (= (logand d 1) 0)
    (setq d (lsh d -1))
  )
  (setq k (paw_mod base d num))
  (if (or (= k 1) (= k n))
    t
    (progn
      (setq tt (/ n 2))
      (while (/= d tt)
(setq d (lsh d 1))
(if (= (paw_mod base d num) n)
  (setq ret t
d tt
  )
)
ret
      )
    )
  )
)

(defun check(p)
  (if (> p 13)
    (cond
      ( (or (= (rem p 2) 0)
    (= (rem p 3) 0)
    (= (rem p 5) 0)
    (= (rem p 7) 0)
    (= (rem p 11) 0)
    (= (rem p 13) 0)
)
        nil
      )
      ( (and (RabbinMiller 2 p)
     (RabbinMiller 7 p)
     (RabbinMiller 5 p)
)
        T
      )
      (t nil)
    )
    (and (member p '(2 3 5 7 11 13)))
  )
)


(check 23421);
nil;