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


isPrime:
; REG USAGE:
; D0 = input (unsigned 32-bit integer)
; D1 = temp storage for D0
; D2 = candidates for possible factors
; D3 = temp storage for quotient/remainder
; D4 = total count of proper divisors.
 
MOVEM.L D1-D4,-(SP)      ;push data regs except D0
MOVE.L #0,D1
MOVEM.L D1,D2-D4         ;clear regs D1 thru D4
 
CMP.L #0,D0
BEQ notPrime
CMP.L #1,D0
BEQ notPrime
CMP.L #2,D0
BEQ wasPrime
 
MOVE.L D0,D1            ;D1 will be used for temp storage.
AND.L #1,D1             ;is D1 even?
BEQ notPrime            ;if so, it's not prime!
 
MOVE.L D0,D1            ;restore D1
 
MOVE.L #3,D2		;start with 3
 
computeFactors:
DIVU D2,D1              ;remainder is in top 2 bytes, quotient in bottom 2.
MOVE.L D1,D3		;temporarily store into D3 to check the remainder
SWAP D3			;swap the high and low words of D3. Now bottom 2 bytes contain remainder.
CMP.W #0,D3		;is the bottom word equal to 0?
BNE D2_Wasnt_A_Divisor	;if not, D2 was not a factor of D1.
 
ADDQ.L #1,D4            ;increment the count of proper divisors.
CMP.L #2,D4             ;is D4 two or greater?
BCC notPrime            ;if so, it's not prime! (Ends early. We'll need to check again if we made it to the end.)
 
D2_Wasnt_A_Divisor:
MOVE.L D0,D1            ;restore D1.
ADDQ.L #1,D2		;increment D2
 
 
CMP.L D2,D1             ;is D2 now greater than D1?
BLS computeFactors      ;if not, loop again
 
CMP.L #1,D4		;was there only one factor?
BEQ wasPrime		;if so, D0 was prime.
 
notPrime:
MOVE.L #0,D0             ;return false
MOVEM.L (SP)+,D1-D4      ;pop D1-D4
RTS
 
wasPrime:
MOVE.L #1,D0             ;return true
MOVEM.L (SP)+,D1-D4      ;pop D1-D4
RTS
;end of program