Eratosthenes Sieve
Procedure
- Included for your review is an implementation of Eratosthenes in C++. Please review and ask any questions you have about this program.
- Remove the eratosthenes implementation (everything in brackets
{}) and add a semicolon to create a forward declaration. - Write Eratosthenes in ARM Assembly, making the following improvements:
- Booleans in C++ are stored in entire bytes. Replace the isNotPrime boolean array with a bitvector (still a large chunk of memory, but internally, you will use only 1 bit to represent each bool/number being prime). To do so, make
isNotPrimeauint32_t*instead of abool*. Adjust the size of isNotPrime to be correct. - Since 2 is the only even number, it is pointless to process even numbers (just creating a special case for 2).
- It is also pointless to store even numbers; removing their storage will reduce the required storage by a factor of 2. eg. if you are given an input of
10, only store and process3, 5, 7, 9.
- Booleans in C++ are stored in entire bytes. Replace the isNotPrime boolean array with a bitvector (still a large chunk of memory, but internally, you will use only 1 bit to represent each bool/number being prime). To do so, make
- Do not move any functionality in or out of the main or eratosthenes methods. The entirity of eratosthenes must be written in Assembly.
- Your program must be capable of running on a Raspberry Pi and be able to consistently process an input of 1 billion (1000000000) in under 5 minutes.