Task

Write a boolean function that tells whether a given integer is prime using Wilson's theorem.

By Wilson's theorem, a number p is prime if and only if p divides (p - 1)! + 1.

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



See also

 Cut-the-knot: Wilson's theorem.
 Wikipedia: Wilson's theorem


	cpu	8086
	org	100h
section	.text
	jmp	demo
	;;;	Wilson primality test of CX.
	;;;	Zero flag set if CX prime. Destroys AX, BX, DX.
wilson:	xor	ax,ax		; AX will hold intermediate fac-mod value
	inc	ax
	mov	bx,cx		; BX = factorial loop counter
	dec	bx
.loop:	mul	bx		; DX:AX = AX*BX
	div	cx		; modulus goes in DX
	mov	ax,dx
	dec	bx		; Next value
	jnz	.loop		; If not zero yet, go again
	inc	ax		; fac-mod + 1 equal to input?
	cmp	ax,cx		; Set flags according to result
	ret
	;;;	Demo: print primes under 256
demo:	mov	cx,2
.loop:	call	wilson		; Is it prime?
	jnz	.next		; If not, try next number
	mov	ax,cx
	call	print		; Otherwise, print the number
.next:	inc	cl		; Next number.
	jnz	.loop		; If <256, try next number
	ret
	;;;	Print value in AX using DOS syscall
print:	mov	bp,10		; Divisor
	mov	bx,numbuf	; Pointer to buffer
.digit:	xor	dx,dx
	div	bp		; Divide AX and get digit in DX
	add	dl,'0'		; Make ASCII
	dec	bx		; Store in buffer
	mov	[bx],dl
	test	ax,ax		; Done yet?
	jnz	.digit		; If not, get next digit
	mov	dx,bx		; Print buffer
	mov	ah,9		; 9 = MS-DOS syscall to print a string
	int	21h
	ret
section	.data
	db	'*****'		; Space to hold ASCII number for output
numbuf:	db	13,10,'$'