Is PrimeΒΆ

Tests whether a number is prime.

 1; Is prime: check if 17 is a prime number using trial division
 2; Tests divisibility by all numbers from 2 to n/2
 3; Registers: R16 = result (1=prime, 0=not prime), R17 = n, R18 = divisor, R19-R20 = temp
 4; Output: R16 = 1 (17 is prime)
 5
 6start:
 7    ldi r17, 17       ; n = 17 (number to test for primality)
 8    
 9    ; special cases: numbers <= 1 are not prime
10    cpi r17, 2
11    brlt not_prime    ; branch if n < 2
12    
13    ; special case: 2 is prime (smallest prime)
14    cpi r17, 2
15    breq is_prime
16    
17    ; test divisibility: check divisors from 2 to n/2
18    ldi r18, 2        ; divisor = 2 (start with smallest prime)
19
20check_loop:
21    ; optimization: if divisor * 2 > n, no need to continue
22    mov r19, r18
23    ldi r20, 2
24    mul r19, r20      ; r19 = divisor * 2
25    cp r19, r17       ; compare with n
26    brge is_prime     ; if divisor * 2 > n, number is prime
27    
28    ; check if n is divisible by current divisor: n % divisor == 0
29    mov r19, r17
30    div r19, r18      ; r19 = n / divisor (quotient)
31    mul r19, r18      ; r19 = quotient * divisor
32    mov r20, r17
33    sub r20, r19      ; r20 = n - (quotient * divisor) = remainder
34    
35    ; if remainder == 0, n is divisible (not prime)
36    cpi r20, 0
37    breq not_prime
38    
39    ; try next divisor
40    inc r18           ; divisor++
41    jmp check_loop
42
43is_prime:
44    ldi r16, 1        ; result = 1 (number is prime)
45    jmp done
46
47not_prime:
48    ldi r16, 0        ; result = 0 (number is not prime)
49
50done:
51    jmp done          ; infinite loop (halt)

Demonstrates trial division and number theory concepts.