This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.


The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.



Task

Implement the   Sieve of Eratosthenes   algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found.

That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes.

If there's an easy way to add such a wheel based optimization, implement it as an alternative version.



Note

 It is important that the sieve algorithm be the actual algorithm used to find prime numbers for the task.


Related tasks

   Emirp primes
   count in factors
   prime decomposition
   factors of an integer
   extensible prime generator
   primality by trial division
   factors of a Mersenne number
   trial factoring of a Mersenne number
   partition an integer X into N primes
   sequence of primes by Trial Division


 
 
/* ARM assembly Raspberry PI  */
/*  program cribleEras.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 MAXI,      101
 
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
sMessResult:        .asciz "Prime  : @ \n"
szCarriageReturn:   .asciz "\n"
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss  
sZoneConv:                  .skip 24
TablePrime:                 .skip   4 * MAXI 
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                               @ entry of program 
    ldr r4,iAdrTablePrime           @ address prime table
    mov r0,#2                       @ prime 2
    bl displayPrime
    mov r1,#2
    mov r2,#1
1:                                  @ loop for multiple of 2
    str r2,[r4,r1,lsl #2]           @ mark  multiple of 2
    add r1,#2
    cmp r1,#MAXI                    @ end ?
    ble 1b                          @ no loop
    mov r1,#3                       @ begin indice
    mov r3,#1
2:
    ldr r2,[r4,r1,lsl #2]           @ load table élément
    cmp r2,#1                       @ is prime ?
    beq 4f
    mov r0,r1                       @ yes -> display
    bl displayPrime
    mov r2,r1
3:                                  @ and loop to mark multiples of this prime
    str r3,[r4,r2,lsl #2]
    add r2,r1                       @ add the prime
    cmp r2,#MAXI              @ end ?
    ble 3b                          @ no -> loop
4:
    add r1,#2                       @ other prime in table
    cmp r1,#MAXI              @ end table ?
    ble 2b                          @ no -> loop
 
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
iAdrsMessResult:         .int sMessResult
iAdrTablePrime:          .int TablePrime
 
/******************************************************************/
/*      Display prime table elements                                */ 
/******************************************************************/
/* r0 contains the prime */
displayPrime:
    push {r1,lr}                    @ save registers
    ldr r1,iAdrsZoneConv
    bl conversion10                 @ call décimal conversion
    ldr r0,iAdrsMessResult
    ldr r1,iAdrsZoneConv            @ insert conversion in message
    bl strInsertAtCharInc
    bl affichageMess                @ display message
100:
    pop {r1,lr}
    bx lr
iAdrsZoneConv:                   .int sZoneConv  
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 