Prime factors

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

.syntax unified

@ 600851475143 is 8BE589EAC7 in hex

.equ numhi,139        @ 0x8b
.equ numlo,3851020999 @ 0xe589eac7

num_hi  .req r4
num_lo  .req r5
maxdiv  .req r6
n       .req r7

.section .rodata
 .align 2
resstring:
 .asciz "%d\n"
.text
 .align 2
 .global main
 .type main, %function
main:
 stmfd sp!, {r4-r7, lr}

 mov maxdiv, 0
 mov n, 1
 ldr num_lo, =numlo
 ldr num_hi, =numhi
loop:
 add n, n, 2           @ start at 3 and increment by 2
loop1:
 mov r0, num_lo
 mov r1, num_hi
 mov r2, n
 mov r3, 0
 bl  long_divide
 teq r2, 0
 bne loop
 teq r3, 0
 bne loop
 mov num_lo, r0         @ only get here when we have no remainder
 mov num_hi, r1         @ save the divisor as the new number
 mov r0, n
 bl isprime
 teq r0, 1
 bne loop               @ increment n if n is non-prime
 cmp maxdiv, n
 movlt maxdiv, n        @ save n as the largest divisor if it is larger
 teq num_lo, 1          @ we know it has prime factors
 beq printme
 b loop1
printme:
 mov r1, maxdiv
 ldr r0, =resstring     @ store address of start of string to r0
 bl printf

 mov r0, 0
 ldmfd sp!, {r4-r7, pc}
 mov r7, 1              @ set r7 to 1 - the syscall for exit
 swi 0                  @ then invoke the syscall from linux

The ARM is a RISC microprocessor and does not provide a divide command in the instruction set. We use a division routine from libgcc.

Using the -S option to gcc when a c file is compiled will generate an assembly language file which can be read for enlightenment.

isprime.s
.syntax unified

# this subroutine returns 1 if the passed number is prime; 0 if not

# inputs
#   r0 - integer to test

# outputs
#   r0 - prime boolean

number   .req r4
divisor  .req r5
tmp      .req r6

.global isprime
.type isprime, %function
.text
.align 2

isprime:
 stmfd sp!, {r4-r6, lr}
 mov number, r0
 ands tmp, number, 1
 bne odd
 mov r0, 0
 cmp number, 2                          @ 2 is the only prime even number
 bne last
 mov r0, 1
 b last
odd:
 mov divisor, 3
 cmp  number, 8
 bgt big
 mov r0, 1
 cmp number, 1                          @ 1 is the only odd number < 8 not prime
 bne last
 mov r0, 0
 b last
big:
 mov r0, number
 mov r1, divisor
 bl divide
 teq r1, 0
 beq factor
 add divisor, divisor, 2
 mul tmp, divisor, divisor
 subs tmp, tmp, number
 ble big
 mov r0, 1
 b last
factor:
 mov r0, 0
last:
 ldmfd sp!, {r4-r6, pc}

The isprime function uses a naive, yet straightforward, algorithm to determine whether a given number is prime.

divide.s
.syntax unified
# divide takes value in r0, divisor in r1 and returns dividend in r0 and modulus
 in r1 
 .global divide
 .type divide, %function
divide:
 stmfd   sp!, {lr}
# see http://infocenter.arm.com/help/topic/com.arm.doc.ihi0043d/IHI0043D_rtabi.pdf
 bl __aeabi_uidivmod
 ldmfd   sp!, {pc}

Our divide and long_divide routines are wrappers around the libgcc functions to allow comments.

long_divide.s

.syntax unified
# long_divide takes low numerator in r0, high numerator in r1, low denominator in r2 and high denominator in r3
# returns low quotient in r0, high quotient in r1, low remainder in r2 and high remainder in r3
.global long_divide
.type long_divide, %function
long_divide:
        stmfd   sp!, {lr}
# see https://codereview.chromium.org/5302007/diff/12001/arch/arm/lib/_uldivmod.S
 bl __aeabi_uldivmod
 ldmfd   sp!, {pc}