Assignment 04 Solution

Description

You are to write an ARM assembly program that uses the Sieve of Eratosthenes (er-uh-tos-thuh-neez)  algorithm to calculate all prime numbers less than or equal to N, where N is a named constant. A good  description of the algorithm can be found at http://www.geeksforgeeks.org/sieve-of-eratosthenes/.

The program below is a C++ version of the solution.  The first N+1 bytes of memory beginning at address   0x40000000 will correspond to the bool prime[N+1] array.  Each entry in this array will be of type DCB.

The first available full-word boundary address after the end of the prime array will corresponds to the  start of the vector<unsigned int> primes data store.  Each entry in this data store will be of type DCD.   Obviously your program will be unable to actually display the prime numbers as does the C++ version.

Submit your .s file through Canvas.

// C++ program to calculate all primes less than or equal to

// N using Sieve of Eratosthenes.  The primes are stored in a vector

#include <vector>

#include <iostream>

using namespace std;

int main() {

// Create a boolean array “prime[0..N]” and initialize

// all entries it as true. A value in prime[i] will

// finally be false if i is Not a prime, else true.

const unsigned int N = 100;

bool prime[N+1];

for(unsigned int i=0; i<N+1; i++)

prime[i] = true;

for (unsigned int p=2; p*p<=N; p++) {

// If prime[p] is not changed, then it is a prime

if (prime[p] == true) {

// Update all multiples of p

for (unsigned int i=p*2; i<=N; i += p)

prime[i] = false;

}

}

vector<unsigned int> primes;

// Save all primes  in a vector

for (unsigned int p=2; p<=N; p++) {

if (prime[p] == true)

primes.push_back(p);

}

// Display the contents of the vector

for (unsigned int prime : primes)

cout << prime << endl;

return 0;

}