How to resolve the algorithm Sieve of Eratosthenes step by step in the 6502 Assembly programming language

Published on 12 May 2024 09:40 PM
#6502 assembly

How to resolve the algorithm Sieve of Eratosthenes step by step in the 6502 Assembly programming language

Table of Contents

Problem Statement

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

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.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sieve of Eratosthenes step by step in the 6502 Assembly programming language

Source code in the 6502 programming language

ERATOS: STA  $D0      ; value of n
        LDA  #$00
        LDX  #$00
SETUP:  STA  $1000,X  ; populate array
        ADC  #$01
        INX
        CPX  $D0
        BPL  SET
        JMP  SETUP
SET:    LDX  #$02
SIEVE:  LDA  $1000,X  ; find non-zero
        INX
        CPX  $D0
        BPL  SIEVED
        CMP  #$00
        BEQ  SIEVE
        STA  $D1      ; current prime
MARK:   CLC
        ADC  $D1
        TAY
        LDA  #$00
        STA  $1000,Y
        TYA
        CMP  $D0
        BPL  SIEVE
        JMP  MARK
SIEVED: LDX  #$01
        LDY  #$00
COPY:   INX
        CPX  $D0
        BPL  COPIED
        LDA  $1000,X
        CMP  #$00
        BEQ  COPY
        STA  $2000,Y
        INY
        JMP  COPY
COPIED: TYA           ; how many found
        RTS

You may also check:How to resolve the algorithm Empty string step by step in the Z80 Assembly programming language
You may also check:How to resolve the algorithm Execute Brain step by step in the Potion programming language
You may also check:How to resolve the algorithm Binary search step by step in the Maxima programming language
You may also check:How to resolve the algorithm Non-decimal radices/Output step by step in the Go programming language
You may also check:How to resolve the algorithm Ackermann function step by step in the Yabasic programming language