Task

Write a program which counts up from   1,   displaying each number as the multiplication of its prime factors.

For the purpose of this task,   1   (unity)   may be shown as itself.



Example

      2   is prime,   so it would be shown as itself.

      6   is not prime;   it would be shown as   



2
×
3


{\displaystyle 2\times 3}

.
2144   is not prime;   it would be shown as   



2
×
2
×
2
×
2
×
2
×
67


{\displaystyle 2\times 2\times 2\times 2\times 2\times 67}

.



Related tasks

   prime decomposition
   factors of an integer
   Sieve of Eratosthenes
   primality by trial division
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes


 
/* ARM assembly Raspberry PI  */
/*  program countFactors.s   */
 
 /* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
.equ NBFACT,    33
.equ MAXI,      1<<31
 
//.equ NOMBRE, 65537
//.equ NOMBRE, 99999999
.equ NOMBRE, 2144
//.equ NOMBRE, 529
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessNumber:       .asciz "Number @ : "
szMessResultFact:   .asciz "@ "
szCarriageReturn:   .asciz "\n"
szErrorGen:         .asciz "Program error !!!\n"
szMessPrime:        .asciz "This number is prime.\n"
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
sZoneConv:           .skip 24
tbZoneDecom:         .skip 8 * NBFACT          // factor 4 bytes, number of each factor 4 bytes
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                             @ entry of program 
    ldr r7,iNombre                @ number
    mov r0,r7
    ldr r1,iAdrsZoneConv
    bl conversion10               @ call décimal conversion
    ldr r0,iAdrszMessNumber
    ldr r1,iAdrsZoneConv          @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess              @ display message
    mov r0,r7
    ldr r1,iAdrtbZoneDecom
    bl decompFact
    cmp r0,#-1
    beq 98f                       @ error ?
    mov r1,r0
    ldr r0,iAdrtbZoneDecom
    bl displayDivisors
 
    b 100f
98:
    ldr r0,iAdrszErrorGen
    bl affichageMess 
100:                              @ standard end of the program 
    mov r0, #0                    @ return code
    mov r7, #EXIT                 @ request to exit program
    svc #0                        @ perform the system call
iAdrszCarriageReturn:    .int szCarriageReturn
iAdrszMessResultFact:    .int szMessResultFact
iAdrszErrorGen:          .int szErrorGen
iAdrsZoneConv:           .int sZoneConv  
iAdrtbZoneDecom:         .int tbZoneDecom
iAdrszMessNumber:        .int szMessNumber
iNombre:                 .int NOMBRE
/******************************************************************/
/*     display divisors function                         */ 
/******************************************************************/
/* r0 contains address of divisors area */
/* r1 contains the number of area items  */
displayDivisors:
    push {r2-r8,lr}            @ save  registers 
    cmp r1,#0
    beq 100f
    mov r2,r1
    mov r3,#0                   @ indice
    mov r4,r0
1:
    add r5,r4,r3,lsl #3
    ldr r7,[r5]                 @ load factor
    ldr r6,[r5,#4]              @ load number of factor
    mov r8,#0                   @ display factor counter
2:
    mov r0,r7
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call décimal conversion
    ldr r0,iAdrszMessResultFact
    ldr r1,iAdrsZoneConv        @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess            @ display message
    add r8,#1                   @ increment counter
    cmp r8,r6                   @ same factors number ?
    blt 2b
    add r3,#1                   @ other ithem
    cmp r3,r2                   @ items maxi ?
    blt 1b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess 
    b 100f
 
100:
    pop {r2-r8,lr}             @ restaur registers
    bx lr                       @ return
/******************************************************************/
/*     factor decomposition                                               */ 
/******************************************************************/
/* r0 contains number */
/* r1 contains address of divisors area */
/* r0 return divisors items in table */
decompFact:
    push {r1-r8,lr}            @ save  registers
    mov r5,r1
    mov r8,r0                  @ save number
    bl isPrime                 @ prime ?
    cmp r0,#1
    beq 98f                    @ yes is prime
    mov r4,#0                  @ raz indice
    mov r1,#2                  @ first divisor
    mov r6,#0                  @ previous divisor
    mov r7,#0                  @ number of same divisors
2:
    mov r0,r8                  @ dividende
    bl division                @  r1 divisor r2 quotient r3 remainder
    cmp r3,#0
    bne 5f                     @ if remainder <> zero  -> no divisor
    mov r8,r2                  @ else quotient -> new dividende
    cmp r1,r6                  @ same divisor ?
    beq 4f                     @ yes
    cmp r6,#0                  @ no but is the first divisor ?
    beq 3f                     @ yes 
    str r6,[r5,r4,lsl #2]      @ else store in the table
    add r4,r4,#1               @ and increment counter
    str r7,[r5,r4,lsl #2]      @ store counter
    add r4,r4,#1               @ next item
    mov r7,#0                  @ and raz counter
3:
    mov r6,r1                  @ new divisor
4:
    add r7,r7,#1               @ increment counter
    b 7f                       @ and loop
 
    /* not divisor -> increment next divisor */
5:
    cmp r1,#2                  @ if divisor = 2 -> add 1 
    addeq r1,#1
    addne r1,#2                @ else add 2
    b 2b
 
    /* divisor -> test if new dividende is prime */
7: 
    mov r3,r1                  @ save divisor
    cmp r8,#1                  @ dividende = 1 ? -> end
    beq 10f
    mov r0,r8                  @ new dividende is prime ?
    mov r1,#0
    bl isPrime                 @ the new dividende is prime ?
    cmp r0,#1
    bne 10f                    @ the new dividende is not prime
 
    cmp r8,r6                  @ else dividende is same divisor ?
    beq 9f                     @ yes
    cmp r6,#0                  @ no but is the first divisor ?
    beq 8f                     @ yes it is a first
    str r6,[r5,r4,lsl #2]      @ else store in table
    add r4,r4,#1               @ and increment counter
    str r7,[r5,r4,lsl #2]      @ and store counter 
    add r4,r4,#1               @ next item
8:
    mov r6,r8                  @ new dividende -> divisor prec
    mov r7,#0                  @ and raz counter
9:
    add r7,r7,#1               @ increment counter
    b 11f
 
10:
    mov r1,r3                  @ current divisor = new divisor
    cmp r1,r8                  @ current divisor  > new dividende ?
    ble 2b                     @ no -> loop
 
    /* end decomposition */ 
11:
    str r6,[r5,r4,lsl #2]      @ store last divisor
    add r4,r4,#1
    str r7,[r5,r4,lsl #2]      @ and store last number of same divisors
    add r4,r4,#1
    lsr r0,r4,#1               @ return number of table items
    mov r3,#0
    str r3,[r5,r4,lsl #2]      @ store zéro in last table item
    add r4,r4,#1
    str r3,[r5,r4,lsl #2]      @ and zero in counter same divisor
    b 100f
 
 
98: 
    ldr r0,iAdrszMessPrime
    bl   affichageMess
    mov r0,#1                   @ return code
    b 100f
99:
    ldr r0,iAdrszErrorGen
    bl   affichageMess
    mov r0,#-1                  @ error code
    b 100f
100:
    pop {r1-r8,lr}              @ restaur registers
    bx lr
iAdrszMessPrime:           .int szMessPrime
 
/***************************************************/
/*   check if a number is prime              */
/***************************************************/
/* r0 contains the number            */
/* r0 return 1 if prime  0 else */
@2147483647
@4294967297
@131071
isPrime:
    push {r1-r6,lr}    @ save registers 
    cmp r0,#0
    beq 90f
    cmp r0,#17
    bhi 1f
    cmp r0,#3
    bls 80f            @ for 1,2,3 return prime
    cmp r0,#5
    beq 80f            @ for 5 return prime
    cmp r0,#7
    beq 80f            @ for 7 return prime
    cmp r0,#11
    beq 80f            @ for 11 return prime
    cmp r0,#13
    beq 80f            @ for 13 return prime
    cmp r0,#17
    beq 80f            @ for 17 return prime
1:
    tst r0,#1          @ even ?
    beq 90f            @ yes -> not prime
    mov r2,r0          @ save number
    sub r1,r0,#1       @ exposant n - 1
    mov r0,#3          @ base
    bl moduloPuR32     @ compute base power n - 1 modulo n
    cmp r0,#1
    bne 90f            @ if <> 1  -> not prime
 
    mov r0,#5
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#7
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#11
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#13
    bl moduloPuR32
    cmp r0,#1
    bne 90f
 
    mov r0,#17
    bl moduloPuR32
    cmp r0,#1
    bne 90f
80:
    mov r0,#1        @ is prime
    b 100f
90:
    mov r0,#0        @ no prime
100:                 @ fin standard de la fonction 
    pop {r1-r6,lr}   @ restaur des registres
    bx lr            @ retour de la fonction en utilisant lr 
/********************************************************/
/*   Calcul modulo de b puissance e modulo m  */
/*    Exemple 4 puissance 13 modulo 497 = 445         */
/*                                             */
/********************************************************/
/* r0  nombre  */
/* r1 exposant */
/* r2 modulo   */
/* r0 return result  */
moduloPuR32:
    push {r1-r7,lr}    @ save registers  
    cmp r0,#0          @ verif <> zero 
    beq 100f
    cmp r2,#0          @ verif <> zero 
    beq 100f           @ 
1:
    mov r4,r2          @ save modulo
    mov r5,r1          @ save exposant 
    mov r6,r0          @ save base
    mov r3,#1          @ start result
 
    mov r1,#0          @ division de r0,r1 par r2
    bl division32R
    mov r6,r2          @ base <- remainder
2:
    tst r5,#1          @  exposant even or odd
    beq 3f
    umull r0,r1,r6,r3
    mov r2,r4
    bl division32R
    mov r3,r2          @ result <- remainder
3:
    umull r0,r1,r6,r6
    mov r2,r4
    bl division32R
    mov r6,r2          @ base <- remainder
 
    lsr r5,#1          @ left shift 1 bit
    cmp r5,#0          @ end ?
    bne 2b
    mov r0,r3
100:                   @ fin standard de la fonction
    pop {r1-r7,lr}     @ restaur des registres
    bx lr              @ retour de la fonction en utilisant lr    
 
/***************************************************/
/*   division number 64 bits in 2 registers by number 32 bits */
/***************************************************/
/* r0 contains lower part dividende   */
/* r1 contains upper part dividende   */
/* r2 contains divisor   */
/* r0 return lower part quotient    */
/* r1 return upper part quotient    */
/* r2 return remainder               */
division32R:
    push {r3-r9,lr}    @ save registers
    mov r6,#0          @ init upper upper part remainder  !!
    mov r7,r1          @ init upper part remainder with upper part dividende
    mov r8,r0          @ init lower part remainder with lower part dividende
    mov r9,#0          @ upper part quotient 
    mov r4,#0          @ lower part quotient
    mov r5,#32         @ bits number
1:                     @ begin loop
    lsl r6,#1          @ shift upper upper part remainder
    lsls r7,#1         @ shift upper  part remainder
    orrcs r6,#1        
    lsls r8,#1         @ shift lower  part remainder
    orrcs r7,#1
    lsls r4,#1         @ shift lower part quotient
    lsl r9,#1          @ shift upper part quotient
    orrcs r9,#1
                       @ divisor sustract  upper  part remainder
    subs r7,r2
    sbcs  r6,#0        @ and substract carry
    bmi 2f             @ négative ?
 
                       @ positive or equal
    orr r4,#1          @ 1 -> right bit quotient
    b 3f
2:                     @ negative 
    orr r4,#0          @ 0 -> right bit quotient
    adds r7,r2         @ and restaur remainder
    adc  r6,#0 
3:
    subs r5,#1         @ decrement bit size 
    bgt 1b             @ end ?
    mov r0,r4          @ lower part quotient
    mov r1,r9          @ upper part quotient
    mov r2,r7          @ remainder
100:                   @ function end
    pop {r3-r9,lr}     @ restaur registers
    bx lr  
 
 
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 