Task

Write a boolean function that tells whether a given integer is prime.



Remember that   1   and all non-positive numbers are not prime.

Use trial division.

Even numbers greater than   2   may be eliminated right away.

A loop from   3   to   √ n    will suffice,   but other loops are allowed.



Related tasks

   count in factors
   prime decomposition
   AKS test for primes
   factors of an integer
   Sieve of Eratosthenes
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


/* NetRexx */
 
options replace format comments java crossref savelog symbols nobinary
 
parse arg nbr rangeBegin rangeEnd .
 
if nbr = '' | nbr = '.' then do
  if rangeBegin = '' | rangeBegin = '.' then rangeBegin = 1
  if rangeEnd   = '' | rangeEnd   = '.' then rangeEnd   = 100
  if rangeEnd > rangeBegin then direction = 1
                           else direction = -1
 
  say 'List of prime numbers from' rangeBegin 'to' rangeEnd':'
  primes = ''
  loop nn = rangeBegin to rangeEnd by direction
    if isPrime(nn) then primes = primes nn
    end nn
    primes = primes.strip
    say '  'primes.changestr(' ', ',')
    say '  Total number of primes:' primes.words
  end
else do
  if isPrime(nbr) then say nbr.right(20) 'is prime'
                  else say nbr.right(20) 'is not prime'
  end
 
return
 
method isPrime(nbr = long) public static binary returns boolean
 
  ip = boolean
 
  select
    when nbr < 2 then do
      ip = isFalse
      end
    when '2 3 5 7'.wordpos(Rexx(nbr)) \= 0 then do
      -- crude shortcut ripped from the Rexx example
      ip = isTrue
      end
    when  nbr // 2 == 0 | nbr // 3 == 0 then do
      -- another shortcut permitted by the one above
      ip = isFalse
      end
    otherwise do
      nn = long
      nnStartTerm = long 3 -- a reasonable start term - nn <= 2 is never prime
      nnEndTerm = long Math.ceil(Math.sqrt(nbr)) -- a reasonable end term
      ip = isTrue -- prime the pump (pun intended)
      loop nn = nnStartTerm to nnEndTerm by 2
         -- Note: in Rexx and NetRexx "//" is the 'remainder of division operator' (which is not the same as modulo)
        if nbr // nn = 0 then do
          ip = isFalse
          leave nn
          end
        end nn
      end
    end
 
  return ip
 
method isTrue public static returns boolean
  return 1 == 1
 
method isFalse public static returns boolean
  return \isTrue