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


*        Primality by trial division  26/03/2017
PRIMEDIV CSECT
         USING  PRIMEDIV,R13       base register
         B      72(R15)            skip savearea
         DC     17F'0'             savearea
         STM    R14,R12,12(R13)    save previous context
         ST     R13,4(R15)         link backward
         ST     R15,8(R13)         link forward
         LR     R13,R15            set addressability
         LA     R10,PG             pgi=0
         LA     R6,1               i=1
       DO WHILE=(C,R6,LE,=F'50')   do i=1 to 50
         LR     R1,R6                i
         BAL    R14,ISPRIME          call isprime(i)
       IF C,R0,EQ,=F'1' THEN         if isprime(i) then
         XDECO  R6,XDEC                edit i
         MVC    0(4,R10),XDEC+8        output i
         LA     R10,4(R10)             pgi+=4
       ENDIF    ,                    endif
         LA     R6,1(R6)             i++
       ENDDO    ,                  enddo i
         XPRNT  PG,L'PG            print buffer
         L      R13,4(0,R13)       restore previous savearea pointer
         LM     R14,R12,12(R13)    restore previous context
         XR     R15,R15            rc=0
         BR     R14                exit
*------- ----   ----------------------------------------
ISPRIME  EQU    *                  function isprime(n)
       IF C,R1,LE,=F'1' THEN       if n<=1 then
         LA     R0,0                 return(0)
         BR     R14                  return
       ENDIF    ,                  endif
       IF C,R1,EQ,=F'2' THEN       if n=2 then
         LA     R0,1                 return(1)
         BR     R14                  return
       ENDIF    ,                  endif
         LR     R4,R1              n
         N      R4,=X'00000001'    n and 1
       IF LTR,R4,Z,R4 THEN         if mod(n,2)=0 then
         LA     R0,0                 return(0)
         BR     R14                  return
       ENDIF    ,                  endif
         LA     R7,3               j=3
         LA     R5,9               r5=j*j
       DO WHILE=(CR,R5,LE,R1)      do j=3 by 2 while j*j<=n
         LR     R4,R1                n
         SRDA   R4,32                ~
         DR     R4,R7                /j
       IF LTR,R4,Z,R4 THEN           if mod(n,j)=0 then
         LA     R0,0                   return(0)
         BR     R14                    return
       ENDIF    ,                    endif
         LA     R7,2(R7)             j+=2
         LR     R5,R7                j
         MR     R4,R7                r5=j*j
       ENDDO    ,                  enddo j
         LA     R0,1               return(1)
         BR     R14                return
*------- ----   ----------------------------------------
PG       DC     CL80' '            buffer
XDEC     DS     CL12               temp for xdeco
         YREGS
         END    PRIMEDIV