$isprime() and $iscomposite()

By IllogicTC on Apr 09, 2011

This is an identifier snippet that will return $true or $false depending on if a given integer is a prime number or not.

For those not in the know, a prime number is a number that only has two natural divisors: 1 and itself. In other words, if you divide the prime number by any other number it will return a number that also has a fraction.

The usage for this snippet is $isprime(N), where N is the number to test. The number must be an integer and can not be negative, or the identifier will return $null.

An example of how this works:

$isprime(3) = $true
The only natural (no fractions) numbers you can multiply that equal 3 is 1 and 3.

$isprime(25) = $false
Not only can you multiply 1 and 25 to get this number, but you could also multiply 5 by 5. Therefore, this number is not prime.

Also included is the identifier $iscomposite(), which inverts the result of $isprime() since any natural number is either prime or composite.

alias isprime {
  if ($chr(46) isin $1) || ($1 < 2) return $null
  if ($1 < 4) return $true
  if ($1 > 3) {
    if ($chr(46) !isin $calc($1 / 2)) return $false
    var %x 1
    var %y $floor($sqrt($1))
    while (%x < %y) {
      inc %x 2
      if (%x // $1) return $false
    }
    return $true
  }
}

alias iscomposite {
  if ($isprime($1) == $true) return $false
  else return $true
}

Like Page Follow Author

Comments

IllogicTC - Apr 09, 2011

Updated per suggestions by jaytea. Now took 140 ticks to determine $isprime(31095121) to be $true. Before it got pretty laggy. Also, I always inc first on while loops so I won't forget, so starting at 3 would make it provide a false result for $isprime(9) as %x would equal 5 when it started the check =P.

And yes, I do understand that there are limitations here. And when you get up to very large numbers (some of the largest mIRC will be able to handle), it may become a bottleneck. But hey, if we can't have $isprime and $iscomposite built-in, this is better than nothing for those who may need it! =P

Respond

jaytea - Apr 09, 2011

while the regex method is nifty, it isn't really one to be taken seriously. it is severely limited, especially given mIRC's line length limit (after all, who hasn't memorized prime numbers up to 4,150??) and the algorithm the regex engine applies is inefficient in principle, even with potential optimizations, though still destined to edge out mIRC script for any appropriately sized input.

and though it's not nearly as interesting to examine code size as code speed for this kind of task, you can of course further shorten those aliases:

alias isprime return $istok($regex($str(1,$1),^1?$|^(11+)\1+$),0,1)
alias iscomposite return $iif(!$isprime($1),) $v1

it is probably worth noting that all of these methods yield incorrect results for $iscomposite(0) and $iscomposite(1); 0 and 1 are neither prime nor composite.

TC, i'm sure you realize that such a snippet can't really be made to perform satisfactorily in a language such as mSL, but you could optimize your current algorithm by: starting %x at 3 and increasing it by 2 each iteration, and terminating the loop just after %x exceeds floor(sqrt($1))

Respond

Jethro - Apr 09, 2011

You can use regex to check for prime numbers:

alias isprime {
  return $+($,$iif($regex($str(1,$1),/^1?$|^(11+?)\1+$/),false,true))
}

For the iscomposite alias, you can use $iif() to shrink it a bit:

alias iscomposite {
  return $+($,$iif($isprime($1) == $true,false,true))
}

Note that I didn't make the regex pattern. I've applied it to mIRC.

Respond